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].

[img]
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: Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:
CreatorsEmailORCIDORCID Put Code
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Mutzel, PetraUNSPECIFIEDorcid.org/0000-0001-7621-971XUNSPECIFIED
Odenthal, ThomasUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Scharbrodt, MarkUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
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