Files in this item

FilesDescriptionFormat

application/pdf

application/pdfSTEIGER-THESIS-2017.pdf (358kB)
(no description provided)PDF

Description

Title:Single-face non-crossing shortest paths in planar graphs
Author(s):Steiger, Alexander John
Advisor(s):Erickson, Jeff
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(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].
Issue Date:2017-07-13
Type:Thesis
URI:http://hdl.handle.net/2142/98345
Rights Information:Copyright 2017 Alex Steiger
Date Available in IDEALS:2017-09-29
Date Deposited:2017-08


This item appears in the following Collection(s)

Item Statistics