English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

The thickness of a minor-excluded class of graphs

MPS-Authors

Jünger,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Mutzel,  Petra
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Odenthal,  Thomas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Scharbrodt,  Mark
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

95-1-027.pdf
(Any fulltext), 4MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Jünger, M., Mutzel, P., Odenthal, T., & Scharbrodt, M.(1995). The thickness of a minor-excluded class of graphs (MPI-I-1995-1-027). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-A1D5-0
Abstract
The thickness problem on graphs is $\cal 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 $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.