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. Equivalently, if there exists a collection of k planar graphs, all sharing the same set of vertices, such that the union of these planar graphs equals G, then the thickness of G is at most k. In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals the graph.
A planar graph therefore has thickness one. Graphs of thickness two are called biplanar graphs. The concept of thickness is a measure of how far a graph is from being planar.
History
The concept of thickness originates in the Earth–Moon problem concerning the chromatic number of biplanar graphs, posed in 1959 by Gerhard Ringel, and in a related 1962 conjecture of Frank Harary: every graph on nine points or its complementary graph is non-planar. This problem is equivalent to determining whether the complete graph K₉ is biplanar (it is not, and the conjecture is true). A comprehensive survey of the topic as of 1998 was written by Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt.
Specific graphs
The thickness of the complete graph on n vertices, Kₙ, is
⌊(n + 7)/6⌋,
except when n = 9 or 10, for which the thickness is three.
With some exceptions, the thickness of a complete bipartite graph K_{a,b} is generally
⌈ab / (2(a + b − 2))⌉.
Properties
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.
Graphs of maximum degree d have thickness at most ⌈d/2⌉. This bound cannot be improved: for a d-regular graph with girth at least 2d, the high girth forces any planar subgraph to be sparse, causing its thickness to be exactly ⌈d/2⌉.
Graphs of thickness t with n vertices have at most t(3n − 6) edges. Because this gives them average degree less than 6t, their degeneracy is at most 6t − 1 and their chromatic number is at most 6t. Conversely, if a graph has degeneracy D, then its arboricity and thickness are at most D.
Even in the case t = 2, the precise value of the chromatic number is unknown; this is Gerhard Ringel's Earth–Moon problem. An example by Thom Sulanke shows that, for t = 2, at least 9 colors are needed.
Related problems
Thickness is closely related to the problem of simultaneous embedding. If two or more planar graphs all share the same vertex set, 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 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.
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. However, the connection to arboricity allows the thickness to be approximated to within an approximation ratio of 3 in polynomial time.
References
- Tutte, W. T. (1963), "The thickness of a graph", Indag. Math., 66: 567–577.
- Mutzel, Petra; Odenthal, Thomas; Scharbrodt, Mark (1998), "The thickness of graphs: a survey", Graphs and Combinatorics, 14 (1): 59–73.
- Ringel, Gerhard (1959), Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, Berlin: VEB Deutscher Verlag der Wissenschaften.
- Mansfield, Anthony (1983), "Determining the thickness of graphs is NP-hard", Mathematical Proceedings of the Cambridge Philosophical Society, 93 (1): 9–23.
- Beineke, Lowell W.; Harary, Frank; Moon, John W. (1964), "On the thickness of the complete bipartite graph", Mathematical Proceedings of the Cambridge Philosophical Society, 60 (1): 1–5.
- Weisstein, Eric W., "Graph Thickness", MathWorld – A Wolfram Resource.
