A Force-Directed Algorithm that Preserves Edge Crossing Properties

Bertault, François (1999) A Force-Directed Algorithm that Preserves Edge Crossing Properties. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 351-358 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_36).

Full text not available from this repository.

Abstract

We present an iterative drawing algorithm for undirected graphs, based on a force-directed approach, that preserves edge crossing properties. This algorithm insures that two edges cross in the final drawing if and only if these edges crossed on the initial layout. So no new edge crossings are introduced. We describe applications of this technique to improve classical algorithms for drawing planar graphs and for interactive graph drawing.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_36
Classifications:J Applications > J.999 Others
M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.420 Crossings
M Methods > M.400 Force-directed / Energy-based
ID Code:378

Repository Staff Only: item control page

References

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

P. D. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

T. Fruchterman and E. Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, 21(11):1129-1164, 1991.

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31:7-15, 1989.

G. Kant. Drawing planar graphs using the lmc-ordering. Proc. IEEE Symp. on Foundation of Computer Science, pages 101-110, 1992.

Goos Kant and Hans L. Bodlaender. Triangulating planar graphs while minimizing the maximum degree. Information and Computation, 135(1):1-14, 1997.

P. Mutzel. A fast linear time embedding algorithm based on the Hopcropt-Tarjan planarity test. Technical report, Institut für Informatik, Universität zu Köln, 1992.