Parametric Shortest Paths in Planar Graphs

Abstract

We construct a family of planar graphs $\{G_n{\}}_{n\ge 4}$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ varies in $(-\infty ,+\infty )$, the piece-wise linear cost of the shortest path from $s$ to $t$ has $n^{\Omega (\log n)}$ pieces. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley \& Shah (2001) for general graphs also hold for planar graphs, thereby refuting a conjecture of Nikolova (2009). Gusfield (1980) and Dean (2009) showed that the number of pieces for every $n$-vertex graph with linear edge weights is $n^{\log n+O(1)}$. We generalize this result in two ways. (i) If the edge weights vary as a polynomial of degree at most $d$, then the number of pieces is $n^{\log n+(\alpha (n)+O(1){)}^d}$, where $\alpha (n)$ is the slow growing inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for ${\mathbb{R}}^3$, is $n^{(\log n{)}^2+O(\log n)}$.

39 pages, 4 figures