Incremental convex planarity testing
From MaRDI portal
Publication:1854448
DOI10.1006/inco.2001.3031zbMath1005.05040OpenAlexW1987793752MaRDI QIDQ1854448
Luca Vismara, Giuseppe Di Battista, Roberto Tamassia
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.2001.3031
Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Atomic Embeddability, Clustered Planarity, and Thickenability ⋮ Checking the convexity of polytopes and the planarity of subdivisions (extended abstract) ⋮ Unit-length rectangular drawings of graphs ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Small Point-Sets Supporting Graph Stories ⋮ Small point-sets supporting graph stories ⋮ On-line convex planarity testing ⋮ Average case analysis of fully dynamic connectivity for directed graphs ⋮ Graph Stories in Small Area ⋮ Graph stories in small area ⋮ Bipartite graphs, upward drawings, and planarity ⋮ A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ Counting the number of perfect matchings in \(K_{5}\)-free graphs ⋮ Dynamic algorithms for shortest paths in planar graphs ⋮ Fast incremental planarity testing ⋮ Bounded Embeddings of Graphs in the Plane ⋮ Checking the convexity of polytopes and the planarity of subdivisions ⋮ Faster algorithms for shortest path and network flow based on graph decomposition
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Drawing plane graphs nicely
- How to draw a planar graph on a grid
- Planarity and duality of finite and infinite graphs
- Planar graphs: Theory and algorithms
- Output-sensitive reporting of disjoint paths
- Geometric representations of graphs
- A data structure for dynamic trees
- On-line maintenance of triconnected components with SPQR-trees
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Special issue: graph drawing
- Drawing planar graphs using the canonical ordering
- Bemerkungen zum Vierfarbenproblem
- Alpha-algorithms for incremental planarity testing (preliminary version)
- Convex Representations of Graphs
- Amortized Computational Complexity
- Self-adjusting binary search trees
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Guest Editors' Introduction
- On-Line Planarity Testing
- Dividing a Graph into Triconnected Components
- Graphlet: design and implementation of a graph editor
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
- Dynamic Graph Drawings: Trees, Series-Parallel Digraphs, and Planar $ST$-Digraphs
- On-line Planar Graph Embedding
- Fast incremental planarity testing
- How to Draw a Graph
- Convex Maps
