Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652673 | Electronic Notes in Discrete Mathematics | 2008 | 6 Pages |
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