A bound on the treewidth of planar even-hole-free graphs ?
The class of planar graphs has unbounded treewidth, since the kk k  k grid, ?k?N ? k ? N , is planar and has treewidth k k . So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if G G is an even-hole-free planar graph, then it does not contain a 99 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 49.
even-hole-free graphs planar graphs bounded treewidth forbidden minor