Abstract
To produce high quality drawings of graphs with nodes drawn as shapes it is important to find routes for the edges which do not intersect node boundaries. Recent work in this area involves finding shortest paths in a tangent-visibility graph. However, construction of the full tangent-visibility graph is expensive, at least quadratic time in the number of nodes. In this paper we explore two ideas for achieving faster edge routing using approximate shortest-path techniques.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)
Bentley, J.L.: Multidimensional divide and conquer. Communications of the ACM 23(4), 214–229 (1980)
Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In: STOC 1987: Nineteenth, New York (May 1987)
Dobkin, D.P., Gansner, E.R., Koutsofios, E., North, S.C.: Implementing a general-purpose edge router. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 262–271. Springer, Heidelberg (1997)
Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 153–164. Springer, Heidelberg (2006)
Dwyer, T., Marriott, K., Wybrow, M.: Integrating edge routing into force-directed layout. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 8–19. Springer, Heidelberg (2007)
Dwyer, T., Marriott, K., Wybrow, M.: Topology preserving constrained graph layout. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 230–241. Springer, Heidelberg (2009), http://www.csse.monash.edu.au/~tdwyer/topology.pdf
Freivalds, K.: Curved edge routing. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 126–137. Springer, Heidelberg (2001)
Gansner, E.R., North, S.C.: Improved force-directed layouts. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 364–373. Springer, Heidelberg (1999)
Ghosh, S.K., Mount, D.M.: An output-sensitive algorithm for computing visibility. SIAM Journal on Computing 20(5), 888–910 (1991)
Lauther, U.: Multipole-based force approximation revisited - a simple but fast implementation using a dynamized enclosing-circle-enhanced k-d-tree. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 20–29. Springer, Heidelberg (2007)
Preparata, F.P., Hong, S.J.: Convex hulls of finite sets of points in two and three dimensions. Communications of the ACM 20(2), 87–92 (1977)
Wybrow, M., Marriott, K., Stuckey, P.J.: Incremental connector routing. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 446–457. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dwyer, T., Nachmanson, L. (2010). Fast Edge-Routing for Large Graphs. In: Eppstein, D., Gansner, E.R. (eds) Graph Drawing. GD 2009. Lecture Notes in Computer Science, vol 5849. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11805-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-11805-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11804-3
Online ISBN: 978-3-642-11805-0
eBook Packages: Computer ScienceComputer Science (R0)