{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/98345"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/98345","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Single-face non-crossing shortest paths in planar graphs","abstract":"The student, Alexander Steiger, submitted this Thesis for approval on 2017-07-12 at 16:52.","abstract_html":"The student, Alexander Steiger, submitted this Thesis for approval on 2017-07-12 at 16:52.","abstract_has_math":false,"creators":["Steiger, Alexander John"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Erickson, Jeff"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-09-29T17:56:33Z","date_published":"2017-09-29T17:56:33Z","updated_at":"2026-07-22T22:24:35Z","subjects":["Planar graphs","Non-crossing paths","Shortest paths"],"languages":["en"],"rights":["Copyright 2017 Alex Steiger"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/98345","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Erickson, Jeff"]},{"key":"dc:creator","label":"Author","values":["Steiger, Alexander John"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-09-29T17:56:33Z","2017-07-13","2017-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Planar graphs","Non-crossing paths","Shortest paths"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Alex Steiger"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/98345"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The student, Alexander Steiger, submitted this Thesis for approval on 2017-07-12 at 16:52.","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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Single-face non-crossing shortest paths in planar graphs"]}]}],"canonical_facts":{"dc:contributor":["Erickson, Jeff"],"dc:creator":["Steiger, Alexander John"],"dc:date":["2017-09-29T17:56:33Z","2017-07-13","2017-08"],"dc:description":["The student, Alexander Steiger, submitted this Thesis for approval on 2017-07-12 at 16:52.","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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/98345"],"dc:language":["en"],"dc:rights":["Copyright 2017 Alex Steiger"],"dc:subject":["Planar graphs","Non-crossing paths","Shortest paths"],"dc:title":["Single-face non-crossing shortest paths in planar graphs"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:35Z"}