Title of article :
Even-hole-free planar graphs have bounded treewidth
Author/Authors :
da Silva، نويسنده , , Aline Alves da Silva، نويسنده , , Ana and Linhares Sales، نويسنده , , Clلudia، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2008
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.
Keywords :
Planar graphs , even-hole-free graphs , Treewidth
Journal title :
Electronic Notes in Discrete Mathematics
Journal title :
Electronic Notes in Discrete Mathematics