Fast incremental planarity testing

DOI10.1007/3-540-55719-9_86MaRDI QIDQ5204329zbMATH OpenOpenAlexFDO

Authors Jeffery R. 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

dead nodedecomposition treelabeled treetree data structurevirtual edge

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Incremental convex planarity testing
• Planarity testing revisited
• Hierarchical planarity testing algorithms
• scientific article; zbMATH DE number 3960992
• Improving the running time of embedded upward planarity testing
• Fully dynamic planarity testing with applications
• Fully-dynamic planarity testing in polylogarithmic time
• scientific article; zbMATH DE number 6863595

Cites work

• A linear-time algorithm for a special case of disjoint set union
• Dividing a Graph into Triconnected Components
• Dynamic orthogonal segment intersection search
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient Planarity Testing
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 177843 (Why is no real title available?)
• Incremental convex planarity testing
• Maintenance of triconnected components of graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Two-Triangle Case of the Acquaintance Graph

Cited in

(24)

• 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
• Alpha-algorithms for incremental planarity testing (extended abstract)
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• scientific article; zbMATH DE number 4060744 (Why is no real title available?)
• scientific article; zbMATH DE number 6863594 (Why is no real title available?)
• On-Line Planarity Testing
• On-line Planar Graph Embedding
• A linear algorithm for the maximal planar subgraph problem
• Fully-dynamic planarity testing in polylogarithmic time
• 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
• Faster and simpler online computation of string net frequency
• Dynamic embeddings of dynamic single-source upward planar graphs
• Improving the running time of embedded upward planarity testing

This page was built for publication: Fast incremental planarity testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204329)