The Thickness of Graphs without K5-Minors

Jünger, Michael and Mutzel, Petra and Odenthal, Thomas and Scharbrodt, Mark (1994) The Thickness of Graphs without K5-Minors.
Technical Report , 10 p.


The thickness problem on graphs is NP-hard and only few results concerning this graph invariant are known. Using decomposition theorems of Wagner and Truemper, we show that the thickness of graphs without K5-minors is less than or equal to two. Therefore, the thickness of this class of graphs can be determined with a planarity testing algorithm in linear time.

Download: [img] Postscript
Download (307kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr94-168
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:16