Homotopic  -Oriented Routing

Verbeek, Kevin (2013) Homotopic  -Oriented Routing. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 272-278 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_24).

Full text not available from this repository.


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 Ω(L logκ) links.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_24
Classifications:P Styles > P.600 Poly-line
P Styles > P.999 Others
ID Code:1316

Repository Staff Only: item control page


Bespamyatnikh, S.: Computing homotopic shortest paths in the plane. J. Alg. 49(2), 284–303 (2003)

Cabello, S., de Berg, M., van Kreveld, M.: Schematization of networks. Comp. Geom.: Theory and Appl. 30(3), 223–238 (2005)

Cabello, S., Liu, Y., Mantler, A., Snoeyink, J.: Testing homotopy for paths in the plane. Discrete & Computational Geometry 31, 61–81 (2004)

Cole, R., Siegel, A.: River routing every which way, but loose. In: Proc. 25th Symp. Found. Comp. Sci., pp. 65–73 (1984)

Duncan, C.A., Efrat, A., Kobourov, S.G., Wenk, C.: Drawing with fat edges. Intern. J. Found. Comp. Sci. 17(5), 1143–1163 (2006)

Efrat, A., Kobourov, S.G., Lubiw, A.: Computing homotopic shortest paths efficiently. Comp. Geom.: Theory and Appl. 35(3), 162–172 (2006)

Gao, S., Jerrum, M., Kaufmann, M., Mehlhorn, K., Rülling, W.: On continuous homotopic one layer routing. In: Proc. 4th Symp. Comp. Geom., pp. 392–402 (1988)

Gupta, H., Wenger, R.: Constructing pairwise disjoint paths with few links. ACM Trans. Alg. 3(3), 26 (2007)

Leiserson, C.E., Maley, F.M.: Algorithms for routing and testing routability of planar VLSI layouts. In: Proc. 17th Symp. Theory. Comp., pp. 69–78 (1985)

Maley, F.M.: Single-layer wire routing and compaction. MIT Press, Cambridge (1990)

Merrick, D., Gudmundsson, J.: Path Simplification for Metro Map Layout. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 258–269. Springer, Heidelberg (2007)

Neyer, G.: Line Simplification with Restricted Orientations. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 13–24. Springer, Heidelberg (1999)

Nöllenburg, M., Wolff, A.: Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Transactions on Visualization and Computer Graphics 17(5), 626–641 (2011)

Speckmann, B., Verbeek, K.: Homotopic Rectilinear Routing with Few Links and Thick Edges. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 468–479. Springer, Heidelberg (2010)