A linear algorithm for the maximal planar subgraph problem

DOI10.1007/3-540-60220-8_77MaRDI QIDQ5057449zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• A linear time algorithm for finding maximal planar subgraphs
• A simple recognition of maximal planar graphs
• Computing and Combinatorics
• A simulated annealing algorithm for the maximum planar subgraph problem

Cites work

• scientific article; zbMATH DE number 3877217 (Why is no real title available?)
• scientific article; zbMATH DE number 177843 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Alpha-algorithms for incremental planarity testing (extended abstract)
• An O(m\log n)-Time Algorithm for the Maximal Planar Subgraph Problem
• Computing an st-numbering
• Dynamic orthogonal segment intersection search
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient Planarity Testing
• Fast incremental planarity testing
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(14)

• A branch-and-cut approach to the crossing number problem
• An algorithm for the characterization of the nonplanarity of a maximal graphical partition
• Finding all maximal subsequences with hereditary properties
• A linear time algorithm for finding maximal planar subgraphs
• An optimal algorithm for extracting the regions of a plane graph
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
• A simulated annealing algorithm for the maximum planar subgraph problem
• O(n2) algorithms for graph planarization
• Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph
• On maximal planarization of nonplanar graphs
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• Computing and Combinatorics
• A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
• scientific article; zbMATH DE number 871895 (Why is no real title available?)

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

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