We construct a family of planar graphs ( G n : n 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 such that, as varies in ( − + ) , the piece-wise linear cost of the shortest path from s to t has n ( 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 +( ( n )+ O (1) ) d , where ( n ) is the slowly growing inverse Ackermann function. This upper bound is obtained by appealing to bounds on the length of Davenport-Schinzel sequences.