Thickness (graph theory)
The concept of thickness originates in the Earth–Moon problem on the chromatic number of biplanar graphs, posed in 1959 by Gerhard Ringel,[4] and on a related 1962 conjecture of Frank Harary: Every graph on nine points or its complementary graph is non-planar.
The problem is equivalent to determining whether the complete graph K9 is biplanar (it is not, and the conjecture is true).
[5] A comprehensive[3] survey on the state of the arts of the topic as of 1998 was written by Petra Mutzel, Thomas Odenthal and Mark Scharbrodt.
[6][7] With some exceptions, the thickness of a complete bipartite graph Ka,b is generally:[8][9] 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.
, the high girth forces any planar subgraph to be sparse, causing its thickness to be exactly
One can find an ordering of the vertices of the graph in which each vertex has at most
neighbors that come later than it in the ordering, and assigning these edges to
distinct subgraphs produces a partition of the graph into
, the precise value of the chromatic number is unknown; this is Gerhard Ringel's Earth–Moon problem.
[13] Thickness is closely related to the problem of simultaneous embedding.
[14] 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.
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.
