Single-face non-crossing shortest paths in planar graphs

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

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Steiger, Alexander John

Contributors dc:contributor

• Erickson, Jeff

• Planar graphs
• Non-crossing paths
• Shortest paths

Statement dc:rights

• Copyright 2017 Alex Steiger

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/98345

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F98345