Parametric Shortest Paths in Planar Graphs.

We construct a family of planar graphs {G_n}_n≥4, where G_n has n vertices including a source vertex s, a sink vertex t, and edge weights that change linearly with a parameter λ such that, as λ varies in (-∞,+∞), the piece-wise linear cost of the shortest path from s to t has n^Ω(logn) pieces. This shows that lower bounds obtained by Carstensen (1983) and Mulmuley & Shah (2001) for general graphs also hold for planar graphs, 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+(α(n)+O(1))^d, where α(n) is the inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for R^3, is n^ (log n)^2+O(log n).