Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652563 | Electronic Notes in Discrete Mathematics | 2009 | 8 Pages |
Abstract
Given a simple planar graph with tree-width w and side size of the largest square grid minor g, it is known that g⩽w⩽5g−1. Thus, the side size of the largest grid minor is a constant approximation for the tree-width in planar graphs. In this work we analyze the lower bounds of this approximation. In particular, we present a class of planar graphs with ⌊3g/2⌋−1⩽w⩽⌊3g/2⌋. We conjecture that in the worst case w=2g+o(g). For this conjecture we have two candidate classes of planar graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics