YOMEDIA
ADSENSE
Graph Drawing - Planar Undirected
81
lượt xem 9
download
lượt xem 9
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
The number of distinct embeddings is exponential in the worst case triconnected planar graphs have a unique embedding. The Complexity of Planarity
AMBIENT/
Chủ đề:
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Graph Drawing - Planar Undirected
- Planar Undirected Graphs Graph Drawing 32
- Planar Drawings and Embeddings s a planar embedding is a class of topologically equivalent planar drawings s a planar embedding prescribes s the star of edges around each vertex s the circuit bounding each face s the number of distinct embeddings is exponential in the worst case s triconnected planar graphs have a unique embedding Graph Drawing 33
- The Complexity of Planarity Testing s Planarity testing and constructing a planar embedding can be done in linear time: s depth-first-search [Hopcroft Tarjan 74] [de Fraysseix Rosenstiehl 82] s st-numbering and PQ-trees [Lempel Even Cederbaum 67] [Even Tarjan 76] [Booth Lueker 76] [Chiba Nishizeki Ozawa 85] s The above methods are complicated to understand and implement s Open Problem: s devise a simple and efficient planarity testing algorithm. Graph Drawing 34
- Planar Straight-Line Drawings s [Hopcroft Tarjan 74]: planarity testing and constructing a planar embedding can be done in O(n) time s [Fary 48, Stein 51, Steinitz 34, Wagner 36]: every planar graph admits a planar straight-line drawing s Planar straight-line drawings may need Ω(n2) area s [de Fraysseix Pach Pollack 88, Schnyder 89, Kant 92]: O(n2)-area planar straight-line grid drawings can be constructed in O(n) time Graph Drawing 35
- Planar Straight-Line Drawings: Angular Resolution s O(n2)-area drawings may have ρ = O(1/n2) n 1 s [Garg Tamassia 94]: s Upper bound on the angular resolution: log d ρ = O ----------- - d3 s Trade-off (area vs. angular resolution): A = Ω ( c ρn ) s [Kant 92] Computing the optimal angular resolution is NP-hard. Graph Drawing 36
- Planar Straight-Line Drawings: Angular Resolution s [Malitz Papakostas 92]: the angular resolution depends on the degree only: ----- ρ = Ω d 1 - 7 s Good angular resolution can be achieved for special classes of planar graphs: s outerplanar graphs, ρ = O(1/d) [Malitz Papakostas 92] s series-parallel graphs, ρ = O(1/d ) 2 [Garg Tamassia 94] s nested-star graphs, ρ = O(1/d ) 2 [Garg Tamassia 94] s Open Problems: s can we achieve ρ = O(1/d ) (k a small k constant) for all planar graphs? s can we efficiently compute an approximation of the optimal angular resolution? Graph Drawing 37
- Planar Orthogonal Drawings: Minimization of Bends s given planar graph of degree ≤ 4, we want to find a planar orthogonal drawing of G with the minimum number of bends Graph Drawing 38
- Minimization of Bends in Planar Orthogonal Drawings s [Tamassia 87] 2 s O(n log n)-time bend minimization for fixed embedding s [Di Battista Liotta Vargiu 93] s polynomial-time bend minimization for degree-3 and series-parallel graphs s [Tamassia Tollis 89] s O(n)-time approximation with O(n) bends s [Garg Tamassia 93] s minimization of bends is NP-hard 1 − ε ) bends s approximation with O(opt + n is NP-hard s rectilinear planarity testing is NP-complete Graph Drawing 39
- Network Flow Model s a unit of flow is a 90° angle s a vertex (source) produces 4 units 1 2 1 s a face f (sink) consumes 2 deg(f) − 4 units (deg(f) + 4 for the external face) 1 1 1 2 1 1 1 s Edges transport flow across faces Graph Drawing 40
- Flow Network s vertex-face arcs: flow ≥ 1, cost = 0 1 2 1 1 3 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 Graph Drawing 41
- Flow Network s face-face arcs: flow ≥ 0, cost = 1 2 1 1 1 1 1 1 1 Graph Drawing 42
- Complete Flow Network 14 2 4 4 4 1 2 3 Graph Drawing 43
- Correctness of Flow Model s supply of sources = demand of sinks ↔ Euler’s formula s flow conservation at vertex ↔ Σ angles around vertex = 360° s flow conservation at face ↔ (# 90° angles) − (# 270° angles) = 4 s cost of flow ↔ # bends s flow in N ↔ drawing of G s minimum cost flow ↔ optimal drawing Theorem [Tamassia 87] Computing the minimum number of bends for an embedded graph G is equivalent to computing a minimum cost flow in network N, and takes O(n2log n) time Open Problem: reduce the time complexity of bend minimization. Graph Drawing 44
- Constrained Bend Minimization s the network flow model allows us to minimize bends subject to shape constraints s prescribed angles around a vertex s prescribed bends along an edge s upper bound on the number of bends on an edge s the above shape constraints on the drawing can be expressed by setting appropriate capacity constraints on the edges of the network s E.g., we can prescribe a maximum of 2 bends on a given edge e by setting equal to 2 the capacity of the face-face arcs associated with e Graph Drawing 45
- Characterization of Bend-Minimal Drawings s A drawing has the minimum number of bends if and only if there is no oriented closed curve C such that s vertices are intersected by C entering from angles ≥ 180° s (# edges crossed by C from 90° or 180°) < (# edges crossed by C from 270°) s If such a curve exists, “rotating” the portion of the drawing inside C reduces the number of bends C Graph Drawing 46
- Proving the Optimality of a Drawing s potential Φ on each face 4 3 2 1 0 5 1 2 3 4 s vertices cannot be traversed by C s C traverses edge from 270° ⇒ ∆Φi = −1 s C traverses edge from 90° ⇒ ∆Φi = +1 s bends removed going ‘‘inward’’ and inserted going ‘‘outward’’ ∆Bi + ∆Φi = 0 s C is a closed curve ⇒ Σi ∆Φi = 0 s Hence, Σi ∆Βi = 0 Graph Drawing 47
- Visibility Representation s vertices → horizontal segments s edges → vertical segments s can be constructed in O(n) time s preliminary step for drawing algorithms Graph Drawing 48
- From Visibility Representations to Orthogonal Drawings Graph Drawing 49
- Heuristic Algorithm for Bend Minimization 1. Construct visibility representation 2. Transform visibility representation into a preliminary drawing 3. Apply bend-stretching transformations 4. Compact orthogonal representation Runs in O(n) time and can be parallelized At most 2n + 4 bends if G is biconnected (2.4n + 2 otherwise) O(n2) area Graph Drawing 50
ADSENSE
CÓ THỂ BẠN MUỐN DOWNLOAD
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
AANETWORK
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn