Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419531 | Discrete Applied Mathematics | 2010 | 11 Pages |
Abstract
The class of planar graphs has unbounded treewidth, since the k×kk×k grid, ∀k∈N∀k∈N, is planar and has treewidth kk. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if GG 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 49.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ana Silva, Aline Alves da Silva, Cláudia Linhares Sales,