Paper by Erik D. Demaine

Reference:

Erik D. Demaine and MohammadTaghi Hajiaghayi, “Bidimensionality, Map Graphs, and Grid Minors”, Manuscript, February 2005.

BibTeX

@Misc{MapGraphGridMinors_Manuscript,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi},
  TITLE         = {Bidimensionality, Map Graphs, and Grid Minors},
  HOWPUBLISHED  = {Manuscript},
  MONTH         = {February},
  YEAR          = 2005,

  comments      = {This paper is also available as
                   <A HREF="http://arxiv.org/abs/cs.DM/0502070">
                   arXiv:cs.DM/0502070</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.},
  length        = {12 pages},
  withstudent   = 1,
}

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]