MPI-I-95-1-027

The thickness problem on graphs is $\cal 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 $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.