MPI-I-95-1-027
The thickness of a minor-excluded class of graphs
Jünger, Michael and Mutzel, Petra and Odenthal, Thomas and Scharbrodt, Mark
October 1995, 9 pages.
.
Status: available - back from printing
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.
-
95-1-027.pdf
- Attachement: MPI-I-95-1-027.ps.gz (69 KBytes); 95-1-027.pdf (3359 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-027
BibTeX
@TECHREPORT{JuengerMutzelOdenthalScharbrodt95,
AUTHOR = {J{\"u}nger, Michael and Mutzel, Petra and Odenthal, Thomas and Scharbrodt, Mark},
TITLE = {The thickness of a minor-excluded class of graphs},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-95-1-027},
MONTH = {October},
YEAR = {1995},
ISSN = {0946-011X},
}