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]

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

${\displaystyle \lfloor \frac{n+7}{6}\rfloor ,}$

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]

${\displaystyle \lceil \frac{ab}{2(a+b-2)}\rceil .}$

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 ${\displaystyle d}$ have thickness at most ${\displaystyle \lceil d/2\rceil }$.^[10] This cannot be improved: for a ${\displaystyle d}$-regular graph with girth at least ${\displaystyle 2d}$, the high girth forces any planar subgraph to be sparse, causing its thickness to be exactly ${\displaystyle \lceil d/2\rceil }$.^[11]

Graphs of thickness ${\displaystyle t}$ with ${\displaystyle n}$ vertices have at most ${\displaystyle t(3n-6)}$ edges. Because this gives them average degree less than ${\displaystyle 6t}$, their degeneracy is at most ${\displaystyle 6t-1}$ and their chromatic number is at most ${\displaystyle 6t}$. 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 ${\displaystyle D}$ then its arboricity and thickness are at most ${\displaystyle D}$. One can find an ordering of the vertices of the graph in which each vertex has at most ${\displaystyle D}$ neighbors that come later than it in the ordering, and assigning these edges to ${\displaystyle D}$ distinct subgraphs produces a partition of the graph into ${\displaystyle D}$ trees, which are planar graphs.

Even in the case ${\displaystyle t=2}$, 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 ${\displaystyle t=2}$, at least 9 colors are needed.^[12]

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

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.

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