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.

Abstract

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.


Actions:
Download: [img] Postscript
Download (300Kb) | Preview
Export as:
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
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/168