A linear algorithm for the maximal planar subgraph problem

DOI10.1007/3-540-60220-8_77zbMath1502.68221OpenAlexW1598585423MaRDI QIDQ5057449

Hristo N. Djidjev

Publication date: 16 December 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60220-8_77

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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 (1)

A branch-and-cut approach to the crossing number problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Computing an st-numbering
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Alpha-algorithms for incremental planarity testing (preliminary version)
• Dynamic orthogonal segment intersection search
• Efficient Planarity Testing
• Efficiency of a Good But Not Linear Set Union Algorithm
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
• Fast incremental planarity testing

This page was built for publication: A linear algorithm for the maximal planar subgraph problem