The thickness of a minor-excluded class of graphs

Jünger, Michael and Mutzel, Petra and Odenthal, Thomas and Scharbrodt, Mark (1998) The thickness of a minor-excluded class of graphs.
Published in: Discrete Mathematics Vol. 182 (1-3). pp. 169-176.


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.

Download: [img] Postscript - Preprinted Version
Download (318kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 9 (Google Scholar) | 2 (Web of Science)
Uncontrolled Keywords: 1-sum 2-sum crossing number decomposition theorem delta-sum graph-minor k5-free graphs planar subgraph skewness thickness topological graph theory
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Additional Information: Graph theory (Lake Bled, 1995)
Related URLs:
Deposit Information:
ZAIK Number: zpr95-201
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 16 Jan 2012 15:50