Single-face non-crossing shortest paths in planar graphs
Alexander John Steiger · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2017
We consider the following problem: Given an n-vertex undirected planar-embedded graph with a simple boundary cycle, non-negative edge lengths, and k pairs of terminals {(s_1,t_1),(s_2,t_2),...,(s_k,t_k)} specified on the boundary, find non-crossing shortest paths connecting all pairs of terminals (if any such paths exist). We present an algorithm to find such paths in O(n log log k) time which improves upon the previous best runtime of O(n log k) by Takahashi, Suzuki, and Nishizeki [Algorithmica 1996].