Graph Drawing - Planar Undirected

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

lượt xem
  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ủ đề:

Nội dung Text: Graph Drawing - Planar Undirected

  1. Planar Undirected Graphs Graph Drawing 32
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. Flow Network s face-face arcs: flow ≥ 0, cost = 1 2 1 1 1 1 1 1 1 Graph Drawing 42
  12. Complete Flow Network 14 2 4 4 4 1 2 3 Graph Drawing 43
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. From Visibility Representations to Orthogonal Drawings Graph Drawing 49
  19. 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



Đồng bộ tài khoản