Graph Drawing - General Undirected

Chia sẻ: Nguyenhoang Phuonguyen | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

88
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 e.g., 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 deﬁne a system of forces acting on the vertices and edges s ﬁnd a minimum energy state (solve differential equations or simulate the evolution of the system)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Graph Drawing - General Undirected

General Undirected Graphs Graph Drawing 58
Algorithmic Strategies for Drawing General Undirected Graphs s 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 e.g., GIOTTO [Tamassia Batini Di Battista 87] s Orientation method s orient the graph into a digraph s use one the drawing algorithms for digraphs s Force-Directed method s deﬁne a system of forces acting on the vertices and edges s ﬁnd a minimum energy state (solve differential equations or simulate the evolution of the system) e.g., 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 60
Topological Constraints in the Planarization Method s a limited constraint satisfaction capability exists within the planarization methods s Example: draw the graph such that the edges in a given set A have no crossings s in Step 1, try adding ﬁrst the edges in A s in Step 3, put a large “crossing cost” on the planar edges in A, and add ﬁrst the nonplanar edges in A (if any) s Example: draw the graph such the vertices of subset U are on the external boundary s add a ﬁctitious vertex v and edges from v to all the vertices in U s let A be the set of edges (u,v), with u in U s impose the above constraint Graph Drawing 61
GIOTTO [Tamassia Di Battista Batini 88] s time complexity: O((N+C)2log N) n tio i za n ar p la n a tio iz n im i m e nd b Graph Drawing 62
30 53 41 28 27 47 11 16 21 44 15 14 20 18 52 29 17 56 22 54 38 63 34 58 45 55 51 31 12 1 9 13 63 61 32 46 3 Graph Drawing 43 40 39 36 59 50 Example 62 42 35 37 4 24 2 25 26 23 33 48 10 5 6 57 8 19 7 49 60
Constraint Satisfaction in GIOTTO s topological constraints s vertices on external face s edges without crossings s grouping of vertices s shape constraints s subgraphs with prescribed orthogonal shape s edges without bends s topological contraints have priority over shape contraints because the algorithm assigns ﬁrst the topology and then the orthogonal shape s grouping is only topological s no position constraints s no length contraints Graph Drawing 64
Advantages and Disadvantages of Planarization Techniques Pro: s fast running time s applicable to straight-line, orthogonal and polyline drawings s supported by theoretical results on planar drawings s works well in practice, also for large graphs s limted constraint satisfaction capability Con: s relatively complex to implement s topological transformations may alter the user’s mental map s difﬁcult to extend to 3D s limted constraint satisfaction capability Graph Drawing 65
The Spring Embedder [Eades 1984] s replace the edges by springs with unit natural length s connect nonadjacent vertices with additional springs with inﬁnite natural length s recall that the springs attract the endpoints when stretched, and repel the endpoints when compressed s start with an initial random placement of the vertices s let the system go ... (assume there is friction so that a stable minimum energy state is eventually reached) Graph Drawing 66
Example s initial conﬁguration s ﬁnal conﬁguration Graph Drawing 67
Other Force-Directed Techniques s [Kamada Kawai 89] s the forces try to place vertices so that their geometric distance in the drawing is equal to their graph-theoretic distance s for each pair of vertices (u,v) use a spring with natural length dist(u,v) s [Fruchterman Reingold 90] s system of forces similar to that of subatomic particles and celestial bodies s given drawing region acts as wall s n-body simulation s [Davidson Harel 89] s energy function takes into account vertex distribution, edge-lengths, and edge-crossings s given drawing region acts as wall s simulated annealing Graph Drawing 68
Examples s drawings of the same graph constructed with the technique of [Davidson Harel 89] using three different energy functions Graph Drawing 69
Advantages and Disadvantages of Force-Directed Techniques Pro: s relatively simple to implement s heuristic improvements easily added s smooth evolution of the drawing into the ﬁnal conﬁguration helps preserving the user’s mental map s can be extended to 3D s often able to detect and display symmetries s works well in practice for small graphs with regular structure s limted constraint satisfaction capability Con: s slow running time s few theoretical results on the quality of the drawings produced s diffcult to extend to orthogonal and polyline drawings s limited constraint satisfaction capability Graph Drawing 70
Constraints in Force-Directed Techniques s position constraints can be easily imposed s we can constrain each vertex to remain in a prescribed region s other constraints can be satisﬁed provided they can be expressed by means of forces, e.g, s “magnetic ﬁeld” to impose orientation constraints [Sugiyama Misue 84] s dummy “attractor” vertex to enforce grouping Graph Drawing 71
Springs for Planar Graphs s use springs with natural length 0, and attractive force proportional to the length s pin down the vertices of the external face to form a given convex polygon (position constraints) s let the system go ... s the ﬁnal conﬁguration is a state of minimum energy: min Σ [ length(e)] 2 e s equivalent to the barycentric mapping [Tutte 60]: p(v) = 1/deg(v) Σ p(w) (v,w) Graph Drawing 72