Dynamic maintenance of planar digraphs, with applications

DOI10.1007/BF01840401zbMath0697.68026MaRDI QIDQ911751

Franco P. Preparata, Roberto Tamassia

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

on-line algorithmpoint locationplanar subdivisiondynamic data structurecontact-chainplanar st- graphtransitive-closure

Mathematics Subject Classification ID

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