AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

MPI Audience

English

30 Minutes

Saarbrücken

We present combinatorial algorithms for the min-cost flow problem in planar
graphs. Previously, the best known bounds came from algorithms for general
graphs using only that the number of arcs is in $O(n)$. These yield near
quadratic algorithms and subquadratic ones only for special cases, e.g.,
$\tilde{O}(n^{7/4})$ time if the optimum objective value is in $O(n)$, or
$O(n^{3/2})$ time for bounded costs and capacities. We demonstrate techniques
to obtain $O(n^{3/2})$ for planar graphs of bounded degree, constant
capacities, and arbitrary costs, or for bidirected planar graphs of bounded
face sizes, no capacities, and bounded costs. These conditions come from
applications in image processing and in graph drawing, respectively. In the
latter case, our result improves a long standing time bound for minimizing the
number of bends in an orthogonal drawing of a plane graph. Without these
restrictions but with the condition of a linear optimum, we only lose a log-
factor, i.e. we get $O(n^{3/2} \log n)$. With a scaling approach, we obtain
$O( \sqrt{\gamma} n \log^3 n log C)$, where $\gamma$ is the sum over all
capacities and $C$ is the maximum over all costs. [joint work with Sabine
Cornelsen]

Christina Fries

--email hidden

passcode not visible

logged in users only