Abstract
Most diagram editors and graph construction tools provide some form of automatic connector routing, typically providing orthogonal or poly-line connectors. Usually the editor provides an initial automatic route when the connector is created and then modifies this when the connector end-points are moved. None that we know of ensure that the route is of minimal length while avoiding other objects in the diagram. We study the problem of incrementally computing minimal length object-avoiding poly-line connector routings. Our algorithms are surprisingly fast and allow us to recalculate optimal connector routings fast enough to reroute connectors even during direct manipulation of an object’s position, thus giving instant feedback to the diagram author.
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
The Omni Group: OmniGraffle Product Page. Web Page (2002), http://www.omnigroup.com/omnigraffle/
Larsson, A.: Dia Home Page. Web Page (2002), http://www.gnome.org/projects/dia/
Microsoft Corporation: Microsoft Visio Home Page. Web Page (2002), http://office.microsoft.com/visio/
Computer Systems Odessa: ConceptDraw Home Page. Web Page (2002), http://www.conceptdraw.com/
yWorks: yFiles - Java Graph Layout and Visualization Library. Web Page (2005), www.yworks.com/products/yfiles/
AT&T Research: Spline-o-matic library. Web Page (1999), http://www.graphviz.org/Misc/spline-o-matic/
Miriyala, K., Hornick, S.W., Tamassia, R.: An incremental approach to aesthetic graph layout. In: Proceedings of the Sixth International Workshop on Computer-Aided Software Engineering, pp. 297–308. IEEE Computer Society, Los Alamitos (1993)
Lee, D.T.: Proximity and reachability in the plane. PhD thesis, Department of Electrical Engineering, University of Illinois, Urbana, IL (1978)
Welzl, E.: Constructing the visibility graph for n line segments in O(n 2) time. Information Processing Letters 20, 167–171 (1985)
Asano, T., Asano, T., Guibas, L., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica 1, 49–63 (1986)
Overmars, M.H., Welzl, E.: New methods for computing visibility graphs. In: Proceedings of the fourth annual symposium on Computational geometry, pp. 164–171. ACM Press, New York (1988)
Ghosh, S.K., Mount, D.M.: An output-sensitive algorithm for computing visibility. SIAM Journal on Computing 20, 888–910 (1991)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596–615 (1987)
Mitchell, J.S.: Geometric shortest paths and network optimization. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633–701. Elsevier Science Publishers B.V., Amsterdam (2000)
Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Information Processing Letters 23, 71–76 (1986)
Ben-Moshe, B., Hall-Holt, O., Katz, M.J., Mitchell, J.S.B.: Computing the visibility graph of points within a polygon. In: SCG 2004: Proceedings of the twentieth annual symposium on Computational geometry, pp. 27–35. ACM Press, New York (2004)
Dijkstra, E.W.: A note on two problems in connection with graphs. Numerische Mathematik, 269–271 (1959)
Nelson, R.C., Samet, H.: A consistent hierarchical representation for vector data. In: SIGGRAPH 1986: Proceedings of the 13th annual conference on Computer graphics and interactive techniques, pp. 197–206. ACM Press, New York (1986)
Shneiderman, B.: Direct manipulation: A step beyond programming languages. IEEE Computer 16, 57–69 (1983)
Woodberry, O.J.: Knowledge engineering a Bayesian network for an ecological risk assessment. Honours thesis, Monash University, CSSE, Australia (2003), http://www.csse.monash.edu.au/hons/projects/2003/Owen.Woodberry/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wybrow, M., Marriott, K., Stuckey, P.J. (2006). Incremental Connector Routing. In: Healy, P., Nikolov, N.S. (eds) Graph Drawing. GD 2005. Lecture Notes in Computer Science, vol 3843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11618058_40
Download citation
DOI: https://doi.org/10.1007/11618058_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31425-7
Online ISBN: 978-3-540-31667-1
eBook Packages: Computer ScienceComputer Science (R0)