# The Thickness of Graphs without K5-Minors

Jünger, Michael and Mutzel, Petra and Odenthal, Thomas and Scharbrodt, Mark
(1994)
*The Thickness of Graphs without K5-Minors.*

Technical Report
, 10 p.

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

Actions:

Download: |
Postscript
Download (307kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

Content information:

Deposit Information:

ZAIK Number: | zpr94-168 |
---|---|

Depositing User: | Prof. Dr. Michael Jünger |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 19 Jan 2012 11:16 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/168 |