creators_name: Dwyer, Tim
creators_name: Marriott, Kim
creators_name: Wybrow, Michael
editors_name: Kaufmann, Michael
editors_name: Wagner, Dorothea
editors_id: Kaufmann, Michael
editors_id: Wagner, Dorothea
type: confpaper
datestamp: 2007-05-04
lastmod: 2008-09-18 11:09:03
metadata_visibility: show
title: Integrating Edge Routing into Force-Directed Layout
ispublished: pub
subjects: M.400
subjects: G.999
full_text_status: none
abstract: The typical use of force-directed layout  is to create organic-looking,
straight-edge drawings of large graphs while combinatorial techniques are
generally preferred for high-quality layout of small to medium sized graphs.
In this paper we integrate edge-routing techniques into a force-directed layout
method based on constrained stress majorisation.  Our basic procedure takes an
initial layout for the graph, including poly-line paths for the edges, and
improves this layout by moving the nodes to reduce stress and moving edge bend
points to straighten the edges and reduce their overall length. Separation
constraints between nodes and edge bend points are used to ensure that nodes
do not overlap edges or other nodes and that no additional edge
crossings are introduced.
    
date: 2007
date_type: published
series: Lecture notes in Computer Science
publisher: Springer
pagerange: 8-19
refereed: FALSE
referencetext: Fisk, C.J., Isett, D.D.: ACCEL: automated circuit card etching layout. In: DAC'65: Proceedings of the SHARE design automation project, ACM Press (1965) 9.1-9.31.
Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31 (1989) 7-15.
Bertault, F.: A force-directed algorithm that preserves edge crossing properties. In: Proc. 7th Int. Symp. on Graph Drawing (GD'1999). Volume 1731 of LNCS., Springer (1999) 351-358.
Brandes, U., Wagner, D.: Using graph layout to visualize train interconnection data. In: Proc. 6th Int. Symp. on Graph Drawing (GD'1998). Volume 1547 of LNCS., Springer (1998) 44-56.
Finkel, B., Tamassia, R.: Curvilinear graph drawing using the force-directed method. In: Proc. 12th Int. Symp. on Graph Drawing (GD'2004). Volume 3383 of LNCS., Springer (2004) 448-453
Dwyer, T., Koren, Y., Marriott, K.: IPSep-CoLa: An incremental procedure for separation constraint layout of graphs. In: Proc. IEEE Symp. on Information Visualisation (Infovis'06) (To appear 2006).
Gansner, E., Koren, Y., North, S.: Graph drawing by stress majorization. In: Proc. 12th Int. Symp. Graph Drawing (GD'04). Volume 3383 of LNCS., Springer (2004) 239-250.
Fruchterman, T., Reingold, E.M.: Graph drawing by force-directed placement. Software - Practice and Experience 21 (1991) 1129-1164.
Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. In: SODA '01: Proc. of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms, Society for Industrial and Applied Mathematics (2001) 246-255.
Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. Journal of Algebraic Discrete Methods 4 (1983) 312-316.
Harel, D., Sardas, M.: Randomized graph drawing with heavy-duty preprocessing. In: AVI '94: Proceedings of the Workshop on Advanced Visual Interfaces, New York, NY, USA, ACM Press (1994) 19-33.
Wybrow, M., Marriott, K., Stuckey, P.J.: Incremental connector routing. In: Proc. 13th Int. Symp. on Graph Drawing (GD'05). Volume 3843 of LNCS., Springer (2006) 446-457.
Purchase, H.C., Cohen, R.F., James, M.: Validating graph drawing aesthetics. In: Proc. 4th Int. Symp. on Graph Drawing (GD'96), Springer (1996) 435-446.
Ware, C., Purchase, H., Colpoys, L., McGill, M.: Cognitive measurements of graph aesthetics. Information Visualization 1 (2002) 103-110.
Dobkin, D.P., Gansner, E.R., Koutsofios, E., North, S.C.: Implementing a generalpurpose edge router. In: Proc. 5th Int. Symp. on Graph Drawing (GD'97). Volume 1353 of LNCS., Springer (1997) 262-271.
Freivalds, K.: Curved edge routing. In: Proc. of the 13th Int. Symp. on Fundamentals of Computation Theory (FCT '01). Number 2138 in LNCS, Springer (2001) 126-137.
Preparata, F.P., Shamos, M.I. In: Computational Geometry. Springer (1985) 359-365.
Dwyer, T., Marriott, K., Stuckey, P.: Fast node overlap removal. In: Proc. 13th Int. Symp. on Graph Drawing (GD'05). Volume 3843 of LNCS. (2006) 153-164.
citation: Dwyer, Tim and Marriott, Kim and Wybrow, Michael (2007) Integrating Edge Routing into Force-Directed Layout. [Conference Paper]