The thickness of a minor-excluded class of graphs

Jünger, Michael; Mutzel, Petra; Odenthal, Thomas; Scharbrodt, Mark

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

報告書

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

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

95-1-027.pdf
(全文テキスト（全般）), 4MB

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-A1D5-0

要旨

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.