Density and Dense Subgraphs In the proposed
research we will discuss the density of graphs. The density of a graph is the ratio of edges to vertices in the graph. We begin by observing density characteristics of real graphs. We use our
observations to create random graph models that more accurately simulate various attributes of real-world graphs. Then we discuss the well-studied densest subgraph problems. It is of great interest
to find the densest subgraph of a given graph. For example, in a network that models academic collaboration, authors within the densest component of the graph tend to be the most prolific. Finding
the densest subgraph of a given graph is easy, it can be done in polynomial time. However, when the number of vertices in the densest subgraph is restricted, say we wish to find the densest
subgraph on k vertices, the problem becomes much more difficult. This problem is so difficult that in order to make progress toward a PTAS, we must restrict the domain. We consider the restricted
size densest subgraph problems on planar graphs. Finally, we see that this restriction is still difficult, so we consider other "select k'' types of problems, the most promising of which is the
k-MST problem.

Major Advisor: Glencora Borradaile Committee: Prasad
Tadepalli Committee: Alan Fern Committee:
Holly Swisher GCR: Harry Yeh