Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.endm.2009.02.006 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Planar graphs,tree decomposition,tree-width,grid minor | Discrete mathematics,Indifference graph,Combinatorics,Clique-sum,Planar straight-line graph,Chordal graph,Treewidth,Pathwidth,1-planar graph,Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
32 | 1571-0653 | 2 |
PageRank | References | Authors |
0.37 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander Grigoriev | 1 | 203 | 24.23 |
| Bert Marchal | 2 | 9 | 2.94 |
| Natalya Usotskaya | 3 | 2 | 1.72 |