TY - CHAP

T1 - The bidimensional theory of bounded-genus graphs

AU - Demaine, Erik D.

AU - Hajiaghayi, Mohammadtaghi

AU - Thilikos, Dimitrios M.

PY - 2004

Y1 - 2004

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

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

UR - http://www.scopus.com/inward/record.url?scp=35048896664&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048896664&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-28629-5_12

DO - 10.1007/978-3-540-28629-5_12

M3 - Chapter

AN - SCOPUS:35048896664

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 191

EP - 203

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Fiala, Jirí

A2 - Kratochvíl, Jan

A2 - Koubek, Vá clav

PB - Springer Verlag

ER -