Thickness (graph theory)

In graph theory, the thickness of a graph G, denoted by θ(G), is the minimum number of planar subgraphs into which G can be decomposed. In other words, it is the smallest number of planar graphs whose union is G.

A graph is planar if it can be drawn in the plane without any edges crossing. Thus, a planar graph has a thickness of 1. A graph that is not planar must have a thickness of at least 2.

The thickness of a graph is a measure of its non-planarity. A graph with high thickness is "far" from being planar, in the sense that it requires many planar graphs to reconstruct it.

Determining the thickness of a graph is, in general, an NP-hard problem. This means that there is no known polynomial-time algorithm to compute the thickness of an arbitrary graph.

Some well-known results related to graph thickness include:

• The thickness of the complete graph K_n is ⌈(n + 7)/6⌉, except for n = 9, 10 where the thickness is 3.

• The thickness of the complete bipartite graph K_m,n is ⌈mn / (2(m+n-2))⌉.

Graph thickness has applications in areas such as VLSI design, where it is related to the number of layers needed to implement a circuit.