A Force-Directed Algorithm that Preserves Edge Crossing Properties
Lecture notes in computer sciencePublished 1 January 1999
François Bertault
Citations36
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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.
Keywords
Computer Science
Software Practice and ExperienceGraph drawing by force‐directed placement
6,359 Citations1991Thomas M. J. Fruchterman, Edward M. Reingold
A modification of the spring‐embedder model of Eades for drawing undirected graphs with straight edges is presented, developed in analogy to forces in natural systems, for a simple, elegant, conceptually‐intuitive, and efficient algorithm.
Information Processing LettersAn algorithm for drawing general undirected graphs
2,771 Citations1989Tomihisa Kamada, Satoru Kawai
COMBINATORICAHow to draw a planar graph on a grid
644 Citations1990Hubert de Fraysseix, János Pach +1 more
It is shown that any setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar.
Drawing planar graphs using the lmc-ordering
76 Citations1992Goos Kant
The author introduces a method to optimize the required area, minimum angle and number of bends of planar drawings of graphs on a grid and introduces a new type of ordering on the vertices and faces of triconnected planar graphs.
Information and ComputationTriangulating Planar Graphs While Minimizing the Maximum Degree
26 Citations1997Goos Kant, Hans L. Bodlaender
This paper describes a linear algorithm to triangulate planar graphs, for which the maximum degree of the triangulated graph is only a constant larger than the lower bounds, and shows that triangulating one face while minimizing themaximum degree can be achieved in polynomial time.