Paper by Erik D. Demaine
- Erik D. Demaine and MohammadTaghi Hajiaghayi, “Bidimensionality, Map Graphs, and Grid Minors”, Manuscript, February 2005.
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
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.
- This paper is also available as arXiv:cs.DM/0502070 of the Computing Research Repository (CoRR).
- The paper is 12 pages.
- The paper is available in PostScript (266k), gzipped PostScript (96k), and PDF (149k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by