Bidimensionality, Map Graphs, and Grid Minors
<|reference_start|>Bidimensionality, Map Graphs, and Grid Minors: 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.<|reference_end|>
@article{demaine2005bidimensionality,,
    title={Bidimensionality, Map Graphs, and Grid Minors},
    author={Erik D. Demaine and MohammadTaghi Hajiaghayi},
    journal={arXiv preprint arXiv:cs/0502070},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0502070},
    primaryClass={cs.DM cs.DS}
}