## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, September 20, 2012, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Christian Sommer (MIT)

## Simple Cycle Separators and Recursive Decompositions for Planar Graphs

In the first part, we review the basics of planar separators (Lipton-Tarjan) and cycle separators (Miller).

In the second part, I shall give a brief outline of a recent result on recursive separator decompositions (also called r-divisions), obtained in collaboration with Philip N. Klein and Shay Mozes. For a preprint, see: http://www.sommer.jp/rdiv.htm

Given a planar graph G on n vertices and an integer parameter r, an r-division of G with few holes is a decomposition of G into O(n/r) regions of size at most r such that each region contains at most a constant number of faces that are not faces of G (also called holes), and such that, for each region, the total number of vertices on these faces is O(sqrt r).

We provide a linear-time algorithm for computing r-divisions with few holes. In fact, our algorithm computes a structure, called decomposition tree, which represents a recursive decomposition of G that includes r-divisions for essentially all values of r. In particular, given an exponentially increasing sequence r = (r_1,r_2,...), our algorithm can produce a recursive r-division with few holes in linear time.

r-divisions with few holes have been used in efficient algorithms to compute shortest paths, minimum cuts, and maximum flows. Our linear-time algorithm improves upon the decomposition algorithm used in the state-of-the-art algorithm for minimum st-cut (Italiano, Nussbaum, Sankowski, and Wulff-Nilsen, STOC 2011), removing one of the bottlenecks in the overall running time of their algorithm (analogously for minimum cut in planar and bounded-genus graphs).

Information for students and suggested topics for student talks