# Parametric Shortest Paths in Planar Graphs

Preprint · Kshitij Gajjar, Jaikumar Radhakrishnan

- Archive id: arxiv:1811.05115
- Published: 2018-11-13
- arXiv: https://arxiv.org/abs/1811.05115
- Source URL: https://arxiv.org/abs/1811.05115
- PDF: https://arxiv.org/pdf/1811.05115
- Provenance: arxiv

## Abstract

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 $λ$ such that, as $λ$ varies in $(-\\infty,+\\infty)$, the piece-wise linear cost of the shortest path from $s$ to $t$ has $n^{Ω(\\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 + (α(n)+O(1))^d}$, where $α(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)}$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.