Single-face non-crossing shortest paths in planar graphs

Planar graphs;Non-crossing paths;Shortest paths

Steiger, Alexander John ; Erickson ; Jeff

关键词: Planar graphs;    Non-crossing paths;    Shortest paths;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/98345/STEIGER-THESIS-2017.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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