A linear time algorithm for finding maximal planar subgraphs

DOI10.1007/BFB0015441zbMATH Open1517.05167MaRDI QIDQ6487983FDOQ6487983

Authors

Publication date 21 March 2023

Mathematics Subject Classification ID

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

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

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

Cited in

(17)

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

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)