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]Cite error: Closing </ref> missing for <ref> tag and on a related 1962 conjecture of Frank Harary: For any graph on 9 points, either itself or its complementary graph is non-planar. The problem is equivalent to determining whether the complete graph K₉ is biplanar (it is not, and the conjecture is true).^[2] 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.^[4]

Specific graphs

The thickness of the complete graph on n vertices, K_n, is

[math]\displaystyle{ \left \lfloor \frac{n+7}{6} \right\rfloor, }[/math]

except when n = 9, 10 for which the thickness is three.^[5][6]

With some exceptions, the thickness of a complete bipartite graph K_a,b is generally:^[7][8]

[math]\displaystyle{ \left \lceil \frac{ab}{2(a+b-2)} \right \rceil. }[/math]

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.^[4][9]

The graphs of maximum degree [math]\displaystyle{ d }[/math] have thickness at most [math]\displaystyle{ \lceil d/2\rceil }[/math].^[10] This cannot be improved: for a [math]\displaystyle{ d }[/math]-regular graph with girth at least [math]\displaystyle{ 2d }[/math], the high girth forces any planar subgraph to be sparse, causing its thickness to be exactly [math]\displaystyle{ \lceil d/2\rceil }[/math].^[11]

Sulanke's nine-color Earth–Moon map, with adjacencies described by the join of a 6-vertex complete graph and 5-vertex cycle graph (center). Because the adjacencies in this graph are the union of those in two planar maps (left and right) it has thickness two.

Graphs of thickness [math]\displaystyle{ t }[/math] with [math]\displaystyle{ n }[/math] vertices have at most [math]\displaystyle{ t(3n-6) }[/math] edges. Because this gives them average degree less than [math]\displaystyle{ 6t }[/math], their degeneracy is at most [math]\displaystyle{ 6t-1 }[/math] and their chromatic number is at most [math]\displaystyle{ 6t }[/math]. Here, the degeneracy can be defined as the maximum, over subgraphs of the given graph, of the minimum degree within the subgraph. In the other direction, if a graph has degeneracy [math]\displaystyle{ D }[/math] then its arboricity and thickness are at most [math]\displaystyle{ D }[/math]. One can find an ordering of the vertices of the graph in which each vertex has at most [math]\displaystyle{ D }[/math] neighbors that come later than it in the ordering, and assigning these edges to [math]\displaystyle{ D }[/math] distinct subgraphs produces a partition of the graph into [math]\displaystyle{ D }[/math] trees, which are planar graphs.

Even in the case [math]\displaystyle{ t=2 }[/math], the precise value of the chromatic number is unknown; this is Gerhard Ringel's Earth–Moon problem. An example of Thom Sulanke shows that, for [math]\displaystyle{ t=2 }[/math], at least 9 colors are needed.^[12]

Related problems

Thickness is closely related to the problem of simultaneous embedding.Cite error: Closing </ref> missing for <ref> tag

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.^[13] However, the connection to arboricity allows the thickness to be approximated to within an approximation ratio of 3 in polynomial time.

References

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Thickness (graph theory). Read more