A linear time algorithm for finding maximal planar subgraphs

DOI10.1007/BFB0015441zbMATH Open1517.05167MaRDI QIDQ6487983FDOQ6487983

Authors:

Publication date: 21 March 2023

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

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)

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient Planarity Testing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Alpha-algorithms for incremental planarity testing (extended abstract)
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem

Cited In (17)

• A new approximation algorithm for finding heavy planar subgraphs
• Finding all maximal subsequences with hereditary properties
• A subset spanner for Planar graphs, with application to subset TSP
• A new approach to the linearity of testing planarity of graphs
• Connectivity of planar graphs
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
• A linear algorithm for the maximal planar subgraph problem
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• 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
• An algorithm of graph planarity testing and cross minimization
• A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
• Title not available (Why is that?)

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)