The thickness of a minor-excluded class of graphs (Q1379835)

The thickness of a graph \(G\) is the minimum number \(k\) such that the edge set of \(G\) can be partitioned into \(k\) sets so that the graph induced by each set is planar. The thickness problem, asking for the thickness of a given graph, is NP-hard. Using a decomposition theorem of \textit{K. Truemper} [Matroid decomposition, Academic Press, Boston (1992; Zbl 0760.05001)], the authors show that the thickness of the class of graphs without \(G_{12}\) minors is less than or equal to two (and therefore, the same is true for the more well-known class of the graphs without \(K_5\) minors). Consequently, the thickness of this class of graphs can be determined with a planarity testing algorithm in linear time.