Dense graph

Inmathematics,adense graphis agraphin which the number of edges is close to the maximal number of edges (where every pair ofverticesis connected by one edge). The opposite, a graph with only a few edges, is asparse graph.The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.

Thegraph densityof simple graphs is defined to be the ratio of the number of edges|E|with respect to the maximum possible edges.

For undirectedsimple graphs,the graph density is:

$D={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}$

Fordirected,simple graphs, the maximum possible edges is twice that of undirected graphs (as there are two directions to an edge) so the density is:

$D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)}}$

whereEis the number of edges andVis the number of vertices in the graph. The maximum number of edges for an undirected graph is${\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}$,so the maximal density is 1 (forcomplete graphs) and the minimal density is 0 (Coleman & Moré 1983).

For families of graphs of increasing size, one often calls them sparse if$D\rightarrow 0$as$|V|\rightarrow \infty$.Sometimes, incomputer science,a more restrictive definition of sparse is used like$|E|=O(|V|\log |V|)$or even$|E|=O(|V|)$.

Upper density

Upper densityis an extension of the concept of graph density defined above from finite graphs to infinite graphs. Intuitively, an infinite graph has arbitrarily large finite subgraphs with any density less than its upper density, and does not have arbitrarily large finite subgraphs with density greater than its upper density. Formally, the upper density of a graphGis theinfimumof the values α such that the finite subgraphs ofGwith density α have a bounded number of vertices. It can be shown using theErdős–Stone theoremthat the upper density can only be 1 or one of thesuperparticular ratios0,⁠1/2⁠,⁠2/3⁠,⁠3/4⁠,⁠4/5⁠,…⁠n/n+ 1⁠(see, e.g., Diestel, edition 5, p. 189).

Sparse and tight graphs

Lee & Streinu (2008)andStreinu & Theran (2009)define a graph as being(k,l)-sparse if every nonempty subgraph withnvertices has at mostkn−ledges, and(k,l)-tight if it is(k,l)-sparse and has exactlykn−ledges. Thustreesare exactly the(1,1)-tight graphs, forests are exactly the(1,1)-sparse graphs, and graphs witharboricitykare exactly the(k,k)-sparse graphs.Pseudoforestsare exactly the(1,0)-sparse graphs, and theLaman graphsarising inrigidity theoryare exactly the(2,3)-tight graphs.

Other graph families not characterized by their sparsity can also be described in this way. For instance the facts that anyplanar graphwithnvertices has at most3n– 6edges (except for graphs with fewer than 3 vertices), and that any subgraph of a planar graph is planar, together imply that the planar graphs are(3,6)-sparse. However, not every(3,6)-sparse graph is planar. Similarly,outerplanar graphsare(2,3)-sparse and planarbipartite graphsare(2,4)-sparse.

Streinu and Theran show that testing(k,l)-sparsity may be performed in polynomial time whenkandlare integers and0 ≤l< 2k.

For a graph family, the existence ofkandlsuch that the graphs in the family are all(k,l)-sparse is equivalent to the graphs in the family having boundeddegeneracyor having boundedarboricity.More precisely, it follows from a result ofNash-Williams (1964)that the graphs of arboricity at mostaare exactly the(a,a)-sparse graphs. Similarly, the graphs of degeneracy at mostdare$\left(d,{\binom {d+1}{2}}\right)$-sparse graphs (Lick & White 1970).

Sparse and dense classes of graphs

Nešetřil & Ossona de Mendez (2010)considered that the sparsity/density dichotomy makes it necessary to consider infinite graph classes instead of single graph instances. They definedsomewhere densegraph classes as those classes of graphs for which there exists a thresholdtsuch that every complete graph appears as at-subdivision in a subgraph of a graph in the class. To the contrary, if such a threshold does not exist, the class isnowhere dense.Properties of the nowhere dense vs somewhere dense dichotomy are discussed inNešetřil & Ossona de Mendez (2012).

The classes of graphs with bounded degeneracy and of nowhere dense graphs are both included in thebiclique-free graphs,graph families that exclude somecomplete bipartite graphas a subgraph (Telle & Villanger 2012).

See also

• Bounded expansion
• Dense subgraph

References

• Paul E. Black,Sparse graph,fromDictionary of Algorithms and Data Structures,Paul E. Black (ed.),NIST.Retrieved on 29 September 2005.
• Coleman, Thomas F.;Moré, Jorge J. (1983), "Estimation of sparse Jacobian matrices and graph coloring Problems",SIAM Journal on Numerical Analysis,20(1): 187–209,doi:10.1137/0720013.
• Diestel, Reinhard (2005),Graph Theory,Graduate Texts in Mathematics,Springer-Verlag,ISBN3-540-26183-4,OCLC181535575.
• Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs",Discrete Mathematics,308(8): 1425–1437,arXiv:math/0702129,doi:10.1016/j.disc.2007.07.104,MR2392060.
• Nash-Williams, C. St. J. A.(1964), "Decomposition of finite graphs into forests",Journal of the London Mathematical Society,39(1): 12,doi:10.1112/jlms/s1-39.1.12,MR0161333
• Lick, Don R; White, Arthur T (1970)."k-Degenerate graphs".Canadian Journal of Mathematics.22(5): 1082–1096.
• Preiss, first (1998),Data Structures and Algorithms with Object-Oriented Design Patterns in C++,John Wiley & Sons,ISBN0-471-24134-2.
• Nešetřil, Jaroslav;Ossona de Mendez, Patrice(2010), "From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits",European Congress of Mathematics,European Mathematical Society, pp. 135–165
• Nešetřil, Jaroslav;Ossona de Mendez, Patrice(2012),Sparsity: Graphs, Structures, and Algorithms,Algorithms and Combinatorics, vol. 28, Heidelberg: Springer,doi:10.1007/978-3-642-27875-4,ISBN978-3-642-27874-7,MR2920058.
• Streinu, I.;Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms",European Journal of Combinatorics,30(8): 1944–1964,arXiv:math/0703921,doi:10.1016/j.ejc.2008.12.018.
• Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah; Ferragina, Paolo (eds.),Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings,Lecture Notes in Computer Science,vol. 7501, Springer, pp. 802–812,doi:10.1007/978-3-642-33090-2_69.