Jünger, Michael, Mutzel, Petra ORCID: 0000-0001-7621-971X, Odenthal, Thomas and Scharbrodt, Mark (1994). The Thickness of Graphs without K5-Minors. ['eprint_fieldopt_monograph_type_preprint' not defined].

[thumbnail of zpr94-168.pdf]
Preview
 PDF
zpr94-168.pdf
Download (203kB) | Preview

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.

Item Type: Monograph (['eprint_fieldopt_monograph_type_preprint' not defined])
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-546914
Date: 1994
Language: English
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: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54691

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item