tailieunhanh - Graph Drawing - General Undirected

Planarization method s if the graph is nonplanar, make it planar! (by placing dummy vertices at the crossings) s use one of the drawing algorithms for planar graphs ., GIOTTO [Tamassia Batini Di Battista 87] Orientation method s orient the graph into a digraph s use one the drawing algorithms for digraphs Force-Directed method s define a system of forces acting on the vertices and edges s find a minimum energy state (solve differential equations or simulate the evolution of the system) | General Undirected Graphs Graph Drawing 58 Algorithmic Strategies for Drawing General Undirected Graphs Planarization method if the graph is nonplanar make it planar by placing dummy vertices at the crossings use one of the drawing algorithms for planar graphs . giotto Tamassia Batini Di Battista 87 Orientation method orient the graph into a digraph use one the drawing algorithms for digraphs Force-Directed method define a system of forces acting on the vertices and edges find a minimum energy state solve differential equations or simulate the evolution of the system . Spring Embedder Eades 84 Graph Drawing 59 A Simple Planarization Method use an on-line planarity testing algorithm 1. try adding the edges one at a time and divide them into planar accepted and nonplanar rejected 2. construct a planar embedding of the subgraph of the planar edges 3. add the nonplanar edges one at a time to the embedding minimizing each time the number of crossings shortest path in dual graph Graph Drawing .