Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “The Bidimensional Theory of Bounded-Genus Graphs”, SIAM Journal on Discrete Mathematics, volume 20, number 2, 2006, pages 357–371.
Bidimensionality provides a tool for developing subexponential fixed-parameter
algorithms for combinatorial optimization problems on graph families that
exclude a minor. This paper extends the theory of bidimensionality for graphs
of bounded genus (which is a minor-excluding family). Specifically we show
that, for any problem whose solution value does not increase under
contractions and whose solution value is large on a grid graph augmented by a
bounded number of handles, the treewidth of any bounded-genus graph is at most
a constant factor larger than the square root of the problem's solution value
on that graph. Such bidimensional problems include vertex cover, feedback
vertex set, minimum maximal matching, dominating set, edge dominating set,
r-dominating set, connected dominating set, planar set cover, and
diameter. On the algorithmic side, by showing that an augmented grid is the
prototype bounded-genus graph, we generalize and simplify many existing
algorithms for such problems in graph classes excluding a minor. On the
combinatorial side, our result is a step toward a theory of graph contractions
analogous to the seminal theory of graph minors by Robertson and Seymour.
- This paper is also available from SIAM.
- The paper is available in PostScript (613k), gzipped PostScript (222k), and PDF (330k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- BoundedGenus_MFCS2004 (The Bidimensional Theory of Bounded-Genus Graphs)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated December 10, 2018 by