Fast incremental planarity testing

DOI10.1007/3-540-55719-9_86zbMath1427.68255MaRDI 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 tree; tree data structure; labeled tree; virtual edge; dead node

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

Related Items

A linear algorithm for the maximal planar subgraph problem, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, Maintenance of triconnected components of graphs, On-line convex planarity testing, On suffix extensions in suffix trees, The suffix tree of a tree and minimizing sequential transducers, Dynamic planar embeddings of dynamic graphs, Incremental convex planarity testing, Position heaps for Cartesian-tree matching on strings and tries, 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, Constructing LZ78 tries and position heaps in linear time for large alphabets, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding

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