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 language | English |
|---|---|
| Title of host publication | Graph Drawing (20th International Symposium, GD 2012, Redmond WA, USA, September 19-21, 2012. Revised Selected Papers) |
| Editors | W. Didimo, M. Patrignani |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 272-278 |
| ISBN (Print) | 978-3-642-36762-5 |
| DOIs | |
| Publication status | Published - 2013 |
| Event | 20th International Symposium on Graph Drawing (GD 2012) - Redmond, United States Duration: 19 Sept 2012 → 21 Sept 2012 Conference number: 20 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 7704 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | 20th International Symposium on Graph Drawing (GD 2012) |
|---|---|
| Abbreviated title | GD 2012 |
| Country/Territory | United States |
| City | Redmond |
| Period | 19/09/12 → 21/09/12 |
Fingerprint
Dive into the research topics of 'Homotopic C-oriented routing'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver