The thickness of a minor-excluded class of graphs Original Research Article

The thickness problem on graphs is NP-hard and only few results concerning this graph invariant are known. Using a decomposition theorem of Truemper, we show that the thickness of the class of graphs without G12 minors is less than or equal to two (and therefore, the same is true for the more well-known class of the graphs without K5 minors). Consequently, the thickness of this class of graphs can be determined with a planarity testing algorithm in linear time.