A linear time algorithm for finding maximal planar subgraphs

DOI10.1007/BFB0015441MaRDI QIDQ6487983zbMATH OpenFDO

Authors

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015441

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• A linear algorithm for the maximal planar subgraph problem
• An algorithm of graph planarity testing and cross minimization
• A simple recognition of maximal planar graphs
• scientific article; zbMATH DE number 3871391

Cites work

• Alpha-algorithms for incremental planarity testing (extended abstract)
• An O(m\log n)-Time Algorithm for the Maximal Planar Subgraph Problem
• Efficient Planarity Testing
• scientific article; zbMATH DE number 3968606 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(17)

• An algorithm of graph planarity testing and cross minimization
• A new approach to the linearity of testing planarity of graphs
• A new approximation algorithm for finding heavy planar subgraphs
• Connectivity of planar graphs
• A subset spanner for Planar graphs, with application to subset TSP
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• On maximal planarization of nonplanar graphs
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• scientific article; zbMATH DE number 871895 (Why is no real title available?)
• A linear algorithm for the maximal planar subgraph problem
• A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
• Finding all maximal subsequences with hereditary properties
• Computing and Combinatorics
• O(n2) algorithms for graph planarization
• Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph

This page was built for publication: A linear time algorithm for finding maximal planar subgraphs

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