Orthogonal Connector Routing

Wybrow, Michael and Marriott, Kim and Stuckey, Peter J. (2010) Orthogonal Connector Routing. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 219-231 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_22).

Full text not available from this repository.

Abstract

Orthogonal connectors are used in a variety of common network diagrams. Most interactive diagram editors provide orthogonal connectors with some form of automatic connector routing. However, these tools use ad-hoc heuristics that can lead to strange routes and even routes that pass through other objects. We present an algorithm for computing optimal object-avoiding orthogonal connector routings where the route minimizes a monotonic function of the connector length and number of bends. The algorithm is efficient and can calculate connector routings fast enough to reroute connectors during interaction.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_22
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.900 Visibility
G Algorithms and Complexity > G.560 Geometry
ID Code:1113

Repository Staff Only: item control page

References

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)

Dobkin, D.P., Gansner, E.R., Koutsofios, E., North, S.C.: Implementing a generalpurpose edge router. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 262– 271. Springer, Heidelberg (1997)

Dwyer, T., Marriott, K., Stuckey, P.: 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., Stuckey, P.: Fast node overlap removal—correction. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 446–447. Springer, Heidelberg (2007)

Miriyala, K., Hornick, S.W., Tamassia, R.: An incremental approach to aesthetic graph layout. In: CASE 1993, pp. 297–308. IEEE Computer Society, Los Alamitos (1993)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Inc., Englewood Cliffs (1999)

Biedl, T.C., Madden, B., Tollis, I.G.: The three-phase method: A unified approach to orthogonal graph drawing. IJCGA 10(6), 553–580 (2000)

Lee, D., Yang, C., Wong, C.: Rectilinear paths among rectilinear obstacles. Discrete Applied Mathematics 70(3), 185–216 (1996)

Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. John Wiley & Sons, Inc., New York (1990)

Lee, C.Y.: An algorithm for path connections and its applications. IRE Transactions on Electronic Computers EC-10(2), 346–365 (1961)

Wu, Y.F., Widmayer, P., Schlag, M.D.F., Wong, C.K.: Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles. IEEE Transactions on Computers 36(3), 321–331 (1987)

Argyriou, E., Bekos, M., Kaufmann, M., Symvonis, A.: Two polynomial time algorithms for the metro-line crossing minimization problem. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 336–347. Springer, Heidelberg (2009)

Bekos, M., Kaufmann, M., Potika, K., Symvonis, A.: Line crossing minimization on metro maps. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 231–242. Springer, Heidelberg (2008)