Graph Drawing - Planar Undirected

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

Thêm vào BST

Báo xấu

85
lượt xem 10
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

Chủ đề:

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

Lưu

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-ﬁrst-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 efﬁcient 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 efﬁciently 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 ﬁnd 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 ﬁxed 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 ﬂow 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 ﬂow across faces Graph Drawing 40
Flow Network s vertex-face arcs: ﬂow ≥ 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: ﬂow ≥ 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 ﬂow conservation at vertex ↔ Σ angles around vertex = 360° s ﬂow conservation at face ↔ (# 90° angles) − (# 270° angles) = 4 s cost of ﬂow ↔ # bends s ﬂow in N ↔ drawing of G s minimum cost ﬂow ↔ optimal drawing Theorem [Tamassia 87] Computing the minimum number of bends for an embedded graph G is equivalent to computing a minimum cost ﬂow 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 ﬂow 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