Paper by Erik D. Demaine
- Reference:
- Erik D. Demaine and MohammadTaghi Hajiaghayi, “Bidimensionality, Map Graphs, and Grid Minors”, Manuscript, February 2005.
- Abstract:
-
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.
- Comments:
- This paper is also available as arXiv:cs.DM/0502070 of the Computing Research Repository (CoRR).
- Length:
- The paper is 12 pages.
- Availability:
- 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.