Homotopic C-oriented routing

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

We study the problem of finding non-crossing minimum-link C -oriented paths that are homotopic to a set of input paths in an environment with C -oriented obstacles. We introduce a special type of C -oriented paths—smooth paths—and present a 2-approximation algorithm that runs in O(n 2 (n¿+¿log¿)¿+¿k in logn) time, where n is the total number of paths and obstacle vertices, k in is the total number of links in the input, and ¿=|C| . The algorithm also computes an O(¿)-approximation for general C -oriented paths. As a related result we show that, given a set of C -oriented paths with L links in total, non-crossing C -oriented paths homotopic to the input paths can require a total of O(L log¿) links.
Original languageEnglish
Title of host publicationGraph Drawing (20th International Symposium, GD 2012, Redmond WA, USA, September 19-21, 2012. Revised Selected Papers)
EditorsW. Didimo, M. Patrignani
Place of PublicationBerlin
PublisherSpringer
Pages272-278
ISBN (Print)978-3-642-36762-5
DOIs
Publication statusPublished - 2013
Event20th International Symposium on Graph Drawing (GD 2012) - Redmond, United States
Duration: 19 Sep 201221 Sep 2012
Conference number: 20

Publication series

NameLecture Notes in Computer Science
Volume7704
ISSN (Print)0302-9743

Conference

Conference20th International Symposium on Graph Drawing (GD 2012)
Abbreviated titleGD 2012
CountryUnited States
CityRedmond
Period19/09/1221/09/12

Fingerprint

Dive into the research topics of 'Homotopic C-oriented routing'. Together they form a unique fingerprint.

Cite this