Incremental Connector Routing

Wybrow, Michael and Marriott, Kim and Stuckey, Peter J. (2006) Incremental Connector Routing. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 446-457 (Official URL: http://dx.doi.org/10.1007/11618058_40).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/11618058_40
Classifications:M Methods > M.999 Others
M Methods > M.300 Dynamic / Incremental / Online
ID Code:722

Repository Staff Only: item control page

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, IEEE Computer Society (1993) 297-308

Lee, D. T.: Proximity and reachability in the plane. PhD thesis, Department of Electrical Engineering, University of Illinois, Urbana, IL (1987)

Welzl, E.: Constructing the visibility graph for n line segments in O(n^{2}) time. Information Processing Letters 20 (1985) 167-171

Asano, T., Asano, T., Guibas, L., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica 1 (1986) 49-63

Overmars, M. H., Welzl, E.: New methods for computing visibility graphs. In: Proceedings of the fourth annual symposium on Computational geometry, ACM Press (1988) 164-171

Ghosh, S. K., Mount, D. M.: An output-sensitive algorithm for computing visibility. SIAM Journal on Computing 20 (1991) 888-910

Fredman, M. L., Tarjan, R. E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34 (1987) 596-615

Mitchell, J. S.: Geometric shortest paths and network optimization. In Sack, J. R., Urrutia, J., eds.: Handbook of Computational Geometry. Elsevier Science Publishers B.V., Amsterdam (2000) 633-701

Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Information Processing Letters 23 (1986) 71-76

Ben-Moshe, B., Hall-Holt, O., Katz, M. J., Mitchell, J. S. B.: Computing the visibility graph of points within a polygon. In: SCG '04: Proceedings of the twentieth annual symposium on Computational geometry, New York, NY, USA, ACM Press (2004) 27-35

Dijkstra, E. W.: A note on two problems in connection with graphs. Numerische Mathematik (1959) 269-271

Nelson, R. C., Samet, H.: A consistent hierarchical representation for vector data. In: SIGGRAPH '86: Proceedings of the 13th annual conference on Computer graphics and interactive techniques, New York, NY, USA, ACM Press (1986) 197-206

Shneiderman, B.: Direct manipulation: A step beyond programming languages. IEEE Computer 16 (1983) 57-69

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/.