Dynamic maintenance of planar digraphs, with applications
From MaRDI portal
Publication:911751
DOI10.1007/BF01840401zbMath0697.68026MaRDI QIDQ911751
Franco P. Preparata, Roberto Tamassia
Publication date: 1990
Published in: Algorithmica (Search for Journal in Brave)
on-line algorithmpoint locationplanar subdivisiondynamic data structurecontact-chainplanar st- graphtransitive-closure
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
I/O-efficient dynamic planar point location, Lower bounds for dynamic transitive closure, planar point location, and parentheses matching, Dynamic expression trees, An efficient parallel algorithm for shortest paths in planar layered digraphs, Fully Dynamic Transitive Closure in plane dags with one source and one sink, An efficient parallel algorithm for shortest paths in planar layered digraphs, Area requirement and symmetry display of planar upward drawings, Dynamic reachability in planar digraphs with one source and one sink, Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear algorithm for embedding planar graphs using PQ-trees
- A unified approach to visibility representations of planar graphs
- Rectilinear planar layouts and bipolar orientations of planar graphs
- Fundamentals of planar ordered sets
- A linear algorithm to find a rectangular dual of a planar triangulated graph
- Amortized efficiency of a path retrieval data structure
- Representing orders on the plane by translating convex figures
- Finding paths and deleting edges in directed acyclic graphs
- Algorithms for plane representations of acyclic digraphs
- On the vector representation of the reachability in planar directed graphs
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Optimal Point Location in a Monotone Subdivision
- Floorplans, planar graphs, and layouts
- Planar embedding: linear-time algorithms for vertex placement and edge orderings
- Planar Lattices
- Location of a Point in a Planar Subdivision and Its Applications
- Fully Dynamic Point Location in a Monotone Subdivision