Tutte Embedding
Graphs can be used to represent relational information. This is the reason
why it is often useful to draw graphs in order to visualize this relational
information.
Example Tutte Embedding
|
A Tutte embedding is a force directed layout algorithm.
The idea of the algorithm is to place every node into the center
of gravity of its neighbors. All edges are drawn as straight lines.
Force directed layout algorithms model the input graph as
a system of forces and try to find a minimum energy configuration
of this system.
|
The algorithm draws planar graphs without edge crossings.
For planar graphs the regions formed by the edges are convex. The
algorithm can also draw non-planar graphs. |
LEDA Function for Tutte Embedding
Let G=(V,E) be a graph without self loops. TUTTE_EMBEDDING() computes
a Tutte Embedding of G in time O(|V|3).
Example TUTTE_EMBEDDING()
|
See also:
Graph Drawing Algorithms
Algorithms for Planar Graphs
Planar Maps
Graph Algorithms
Graphs
and Related Data Types
Manual Entries:
Manual
Page Graph Drawing Algorithms
|