Thickness (graph theory)
In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the same set of vertices, such that the union of these planar graphs is G, then the thickness of G is at most k.[1][2]
Specific graphs
The thickness of a complete graph on n vertices, Kn, is , except in the cases of K9 and K10 for which the thickness is three.[3][4] With some exceptions, the thickness of a complete bipartite graph Ka,b is generally .[5][6]
Related problems
Every forest is planar, and every planar graph can be partitioned into at most three forests. Therefore, the thickness of any graph G is at most equal to the arboricity of the same graph (the minimum number of forests into which it can be partitioned) and at least equal to the arboricity divided by three.[2][7] The thickness of G is also within constant factors of another standard graph invariant, the degeneracy, defined as the maximum, over subgraphs of G, of the minimum degree within the subgraph. If an n-vertex graph has thickness t then it necessarily has at most t(3n − 6) edges, from which it follows that its degeneracy is at most 6t − 1. In the other direction, if a graph has degeneracy D then it has arboricity, and thickness, at most D.
Thickness is closely related to the problem of simultaneous embedding.[8] If two or more planar graphs all share the same vertex set, then it is possible to embed all these graphs in the plane, with the edges drawn as curves, so that each vertex has the same position in all the different drawings. However, it may not be possible to construct such a drawing while keeping the edges drawn as straight line segments. A different graph invariant, the rectilinear thickness or geometric thickness of a graph G, counts the smallest number of planar graphs into which G can be decomposed subject to the restriction that all of these graphs can be drawn simultaneously with straight edges. The book thickness adds an additional restriction, that all of the vertices be drawn in convex position, forming a circular layout of the graph. However, in contrast to the situation for arboricity and degeneracy, no two of these three thickness parameters are always within a constant factor of each other.[9]
Computational complexity
It is NP-hard to compute the thickness of a given graph, and NP-complete to test whether the thickness is at most two.[10]
References
- ^ Tutte, W. T. (1963), "The thickness of a graph", Indag. Math., 25: 567–577, MR 0157372.
- ^ a b Mutzel, Petra; Odenthal, Thomas; Scharbrodt, Mark (1998), "The thickness of graphs: a survey", Graphs and Combinatorics, 14 (1): 59–73, doi:10.1007/PL00007219, MR 1617664.
- ^ Mutzel, Odenthal & Scharbrodt (1998), Theorem 3.2.
- ^ Alekseev, V. B.; Gončakov, V. S. (1976), "The thickness of an arbitrary complete graph", Mat. Sb. (N.S.), 101(143) (2): 212–230, MR 0460162.
- ^ Mutzel, Odenthal & Scharbrodt (1998), Theorem 3.4.
- ^ Beineke, Lowell W.; Harary, Frank; Moon, John W. (1964), "On the thickness of the complete bipartite graph", Proc. Cambridge Philos. Soc., 60: 1–5, MR 0158388.
- ^ Dean, Alice M.; Hutchinson, Joan P.; Scheinerman, Edward R. (1991), "On the thickness and arboricity of a graph", Journal of Combinatorial Theory, Series B, 52 (1): 147–151, doi:10.1016/0095-8956(91)90100-X, MR 1109429.
- ^ Brass, Peter; Cenek, Eowyn; Duncan, Cristian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna; Mitchell, Joseph S. B. (2007), "On simultaneous planar graph embeddings", Computational Geometry, 36 (2): 117–130, doi:10.1016/j.comgeo.2006.05.006, MR 2278011
{{citation}}: Unknown parameter|displayauthors=ignored (|display-authors=suggested) (help). - ^ Eppstein, David (2004), "Separating thickness from geometric thickness", Towards a theory of geometric graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, pp. 75–86, doi:10.1090/conm/342/06132, MR 2065254.
- ^ Mansfield, Anthony (1983), "Determining the thickness of graphs is NP-hard", Mathematical Proceedings of the Cambridge Philosophical Society, 93 (1): 9–23, doi:10.1017/S030500410006028X, MR 0684270.