Jünger, Michael, Mutzel, Petra ORCID: 0000-0001-7621-971X, Odenthal, Thomas and Scharbrodt, Mark (1998). The thickness of a minor-excluded class of graphs. Discrete Mathematics, 182 (1-3). pp. 169-176. Elsevier.

[thumbnail of zpr95-201.pdf]
Preview
 PDF
zpr95-201.pdf - Submitted Version
Download (180kB) | Preview

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.

Item Type: Article
Creators:
Creators
Email
ORCID
ORCID Put Code
Jünger, Michael
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Mutzel, Petra
UNSPECIFIED
https://orcid.org/0000-0001-7621-971X
UNSPECIFIED
Odenthal, Thomas
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Scharbrodt, Mark
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
URN: urn:nbn:de:hbz:38-546990
Journal or Publication Title: Discrete Mathematics
Volume: 182
Number: 1-3
Page Range: pp. 169-176
Date: 1998
Publisher: Elsevier
Language: German
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/54699

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item