Bidimensionality, Map Graphs, and Grid Minors
| dc.creator | Demaine, Erik D. | |
| dc.creator | Hajiaghayi, MohammadTaghi | |
| dc.date | 2005-02-16 | |
| dc.date.accessioned | 2026-07-07T03:22:33Z | |
| dc.date.available | 2026-07-07T03:22:33Z | |
| dc.description | In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial relation between the treewidth of a graph in the family and the size of the largest grid minor. These bounds improve the running times of a broad class of fixed-parameter algorithms. Our novel technique of using approximate max-min relations between treewidth and size of grid minors is powerful, and we show how it can also be used, e.g., to prove a linear relation between the treewidth of a bounded-genus graph and the treewidth of its dual. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0502070 | |
| dc.identifier | http://arxiv.org/abs/cs/0502070 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32636 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Bidimensionality, Map Graphs, and Grid Minors | |
| dc.type | text |