Article ID Journal Published Year Pages File Type
4652673 Electronic Notes in Discrete Mathematics 2008 6 Pages PDF
Abstract

The class of planar graphs has unbounded treewidth, since the k×k grid, ∀k∈N, is planar and has treewidth k. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if G is an even-hole-free planar graph, then it does not contain a 9 × 9 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 44.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics