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.

Abstract

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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (318kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 9 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
Additional Information: Graph theory (Lake Bled, 1995)
Uncontrolled Keywords: 1-sum, 2-sum, crossing number, decomposition theorem, delta-sum, graph-minor, k5-free graphs, planar subgraph, skewness, thickness, topological graph theory
Subjects: UNSPECIFIED
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 16 Jan 2012 15:50
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 16 Jan 2012 15:50
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/201