2026-09-21T23:52:07Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/98345 2023-07-11 col_2142_10761 col_2142_5131 com_2142_10755 com_2142_234 com_2142_5130

The student, Alexander Steiger, submitted this Thesis for approval on 2017-07-12 at 16:52. Erickson, Jeff Steiger, Alexander John 2017-09-29T17:56:33Z 2017-09-29T17:56:33Z 2017-07-13 2017-08 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]. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo terms The student, Alexander Steiger, accepted the attached license on 2017-07-08 at 13:28. This Thesis was approved for publication on 2017-07-13 at 16:18. DSpace SAF Submission Ingestion Package generated from Vireo submission #11343 on 2017-09-29 at 11:28:27 Made available in DSpace on 2017-09-29T17:56:33Z (GMT). No. of bitstreams: 2 STEIGER-THESIS-2017.pdf: 358042 bytes, checksum: 449148067e5460bcf49e4b924ac6c43e (MD5) LICENSE.txt: 4214 bytes, checksum: 448b59ad5fe37a5e627970f7187ac3b2 (MD5) Previous issue date: 2017-07-13 application/pdf http://hdl.handle.net/2142/98345 en Copyright 2017 Alex Steiger Planar graphs Non-crossing paths Shortest paths Single-face non-crossing shortest paths in planar graphs text text Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.