We construct a family of planar graphs $(G_n: n\geq 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)}$ break points. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley & Shah (2000) for general graphs also hold for planar graphs. A conjecture of Nikolova (2009) states that the number of break points in $n$-vertex planar graphs is bounded by a polynomial in $n$; our result refutes this conjecture.

Gusfield (1980) and Dean (2009) showed that the number of break points for every $n$-vertex graph is $n^{\log n + O(1)}$ assuming linear edge weights; we show that if the edge weights are allowed to vary as a polynomial of degree at most $d$, then the number of break points is $n^{\log n + (\alpha(n)+O(1))^d}$, where $\alpha(n)$ is the slowly growing inverse Ackermann function. This upper bound is obtained by appealing to bounds on the length of Davenport-Schinzel sequences.

This version of the paper differs from the version posted earlier in the following respects. (i) Some minor errors have been corrected. (ii) In the earlier version, the bound of $O((\log n)^3)$ on the bit lengths of the coefficients of the edge weights was argued informally; this version presents a formal argument. Furthermore, the coefficients are now integers, whereas earlier they were rational numbers. (iii) We attempt to provide a treewidth characterization for parametric shortest paths, which was not present in the earlier version. (iv) The appendix contains a proof that the parametric shortest path complexity of a $3 \times n$ grid graph is linear in $n$.

We construct a family of planar graphs $(G_n: n\geq 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$ increases, the cost of the shortest path from $s$ to $t$ has $n^{\Omega(\log n)}$ break points. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley & Shah (2000) for general graphs also hold for planar graphs. A conjecture of Nikolova (2009) states that the number of break points in $n$-vertex planar graphs is bounded by a polynomial in $n$; our result refutes this conjecture.

Gusfield (1980) and Dean (2009) showed that the number of break points for an $n$-vertex graph is $n^{\log n + O(1)}$ assuming linear edge weights; we show that if the edge weights are allowed to vary as a polynomial of degree at most $d$, then the number of break points is $n^{\log n + O(\alpha(n)^d)}$, where $\alpha(n)$ is the slowly growing inverse Ackermann function. This upper bound arises from Davenport-Schinzel sequences.