Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “The Bidimensional Theory of Bounded-Genus Graphs”, in Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Prague, Czech Republic, August 22–27, 2004, pages 191–203.
Bidimensionality is a powerful tool for developing subexponential
fixed-parameter algorithms for combinatorial optimization problems on graph
families that exclude a minor. This paper completes 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. This result has many algorithmic and
combinatorial consequences. 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
- The paper is 12 pages.
- The paper is available in PostScript (483k), gzipped PostScript (193k), and PDF (204k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- BoundedGenus_SIDMA (The Bidimensional Theory of Bounded-Genus Graphs)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 13, 2019 by