The thickness of a minor-excluded class of graphs
type: Item
instance of: scholarly article
title: The thickness of a minor-excluded class of graphs
zbMATH Open document ID: 0888.05046
DOI: 10.1016/S0012-365X(97)00146-5
author: Michael Jünger
author: Petra Mutzel
author: Thomas Odenthal
author: Mark Scharbrodt
published in: Discrete Mathematics
publication date: 1998-05-13T00:00:00Z
review text: The thickness of a graph \(G\) is the minimum number \(k\) such that the edge set of \(G\) can be partitioned into \(k\) sets so that the graph induced by each set is planar. The thickness problem, asking for the thickness of a given graph, is NP-hard. Using a decomposition theorem of \textit{K. Truemper} [Matroid decomposition, Academic Press, Boston (1992; Zbl 0760.05001)], the authors show that the thickness of the class of graphs without \(G_{12}\) minors is less than or equal to two (and therefore, the same is true for the more well-known class of the graphs without \(K_5\) minors). Consequently, the thickness of this class of graphs can be determined with a planarity testing algorithm in linear time.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1121493
zbMATH Keywords: thickness
zbMATH Keywords: crossing number
zbMATH Keywords: skewness
zbMATH Keywords: graph minor
zbMATH Keywords: decomposition
zbMATH Keywords: planar subgraph
reviewed by: Klaus Dohmen
MaRDI profile type: Publication
Wikidata QID: Q56977453
cites work: Q3856672
cites work: On the thickness and arboricity of a graph
cites work: On the thickness of graphs of given degree
cites work: Efficient Planarity Testing
cites work: Determining the thickness of graphs is NP-hard
cites work: Q4004142
cites work: Über eine Eigenschaft der ebenen Komplexe
full work available at URL: s0012-365x(97)00146-5
OpenAlex ID: W1974098410
description: scientific article; zbMATH DE number 1121493