Dynamic maintenance of planar digraphs, with applications
DOI10.1007/BF01840401zbMATH Open0697.68026MaRDI QIDQ911751FDOQ911751
F. 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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Optimal Point Location in a Monotone Subdivision
- Planar Lattices
- Amortized efficiency of a path retrieval data structure
- Location of a Point in a Planar Subdivision and Its Applications
- Algorithms for plane representations of acyclic digraphs
- Fundamentals of planar ordered sets
- A linear algorithm to find a rectangular dual of a planar triangulated graph
- Finding paths and deleting edges in directed acyclic graphs
- Representing orders on the plane by translating convex figures
- On the vector representation of the reachability in planar directed graphs
- Fully Dynamic Point Location in a Monotone Subdivision
- Floorplans, planar graphs, and layouts
- Planar embedding: linear-time algorithms for vertex placement and edge orderings
Cited In (14)
- Dynamic reachability in planar digraphs with one source and one sink
- Generalized core maintenance of dynamic bipartite graphs
- Optimizing planned maintenance graphs for collections of engineering network sections
- Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- Area requirement and symmetry display of planar upward drawings
- Maintaining regular properties dynamically in \(k\)-terminal graphs
- Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
- Dynamic expression trees
- Fully Dynamic Transitive Closure in plane dags with one source and one sink
- Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
- I/O-efficient dynamic planar point location
- Maintenance of triconnected components of graphs
Recommendations
- Title not available (Why is that?) 👍 👎
- Maintenance of a minimum spanning forest in a dynamic plane graph 👍 👎
- Dynamic maintenance of directed hypergraphs 👍 👎
- Maintaining chordal graphs dynamically: improved upper and lower bounds 👍 👎
- Dynamically switching vertices in planar graphs (extended abstract) 👍 👎
- Generalized core maintenance of dynamic bipartite graphs 👍 👎
- Dynamic planar embeddings of dynamic graphs 👍 👎
- Dynamic Planar Embeddings of Dynamic Graphs 👍 👎
- Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs 👍 👎
- Dynamic 2- and 3-connectivity on planar graphs 👍 👎
This page was built for publication: Dynamic maintenance of planar digraphs, with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911751)
