# Rerouting shortest paths in planar graphs

Preprint · Paul Bonsma

- Archive id: arxiv:1204.5613
- Published: 2012-04-25
- arXiv: https://arxiv.org/abs/1204.5613
- Source URL: https://arxiv.org/abs/1204.5613
- PDF: https://arxiv.org/pdf/1204.5613
- Provenance: arxiv

## Abstract

A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. To this end, we introduce a dynamic programming method for reconfiguration problems.

_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.