Universität zu Köln

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.

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:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED 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