University of Illinois Urbana-Champaign

Single-face non-crossing shortest paths in planar graphs

Steiger, Alexander John

Permalink

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

Description

Title
Single-face non-crossing shortest paths in planar graphs
Author(s)
Steiger, Alexander John
Issue Date
2017-07-13
Director of Research (if dissertation) or Advisor (if thesis)
Erickson, Jeff
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
  • Planar graphs
  • Non-crossing paths
  • Shortest paths
Abstract
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].
Graduation Semester
2017-08
Type of Resource
text
Permalink
http://hdl.handle.net/2142/98345
Copyright and License Information
Copyright 2017 Alex Steiger

Owning Collections

Dissertations and Theses - Computer Science
Dissertations and Theses from the Dept. of Computer Science
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois