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 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.

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 BibTeX file.
Last updated July 23, 2024 by Erik Demaine.