Fast incremental planarity testing

DOI10.1007/3-540-55719-9_86zbMath1427.68255OpenAlexW1550834367MaRDI QIDQ5204329

Jeffery Westbrook

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55719-9_86

zbMATH Keywords

decomposition treetree data structurelabeled treevirtual edgedead node

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Data structures (68P05)

Related Items

A linear algorithm for the maximal planar subgraph problem, Position heaps for Cartesian-tree matching on strings and tries, The suffix tree of a tree and minimizing sequential transducers, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, Dynamic planar embeddings of dynamic graphs, On-line convex planarity testing, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, On suffix extensions in suffix trees, Maintenance of triconnected components of graphs, Efficient computation of longest single-arm-gapped palindromes in a string, Fully-online suffix tree and directed acyclic word graph construction for multiple texts, Efficient dynamic dictionary matching with DAWGs and AC-automata, Incremental convex planarity testing, Constructing LZ78 tries and position heaps in linear time for large alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incremental convex planarity testing
• Fast Algorithms for Finding Nearest Common Ancestors
• Dynamic orthogonal segment intersection search
• Efficient Planarity Testing
• Efficiency of a Good But Not Linear Set Union Algorithm
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Dividing a Graph into Triconnected Components
• Maintenance of triconnected components of graphs
• The Two-Triangle Case of the Acquaintance Graph