A Linear-Time Algorithm for Finding a Maximal Planar Subgraph

DOI10.1137/S0895480197328771MaRDI QIDQ3440266zbMATH OpenOpenAlexFDO

Authors Hristo N. Djidjev

Publication date 22 May 2007

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480197328771

zbMATH Keywords

data structuresgraph planarizationincremental algorithmsplanar graphsplanarity testingtriconnectivity

Mathematics Subject Classification ID

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

Recommendations

• A linear algorithm for the maximal planar subgraph problem
• A linear time algorithm for finding maximal planar subgraphs
• Computing and Combinatorics
• scientific article; zbMATH DE number 871895
• A simple recognition of maximal planar graphs

Cited in

(21)

• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• A new approach to the linearity of testing planarity of graphs
• A new approximation algorithm for finding heavy planar subgraphs
• Edge-orders
• The spanning maximal planar subgraph problem for some classes of complete 4-partite graphs
• Alpha-algorithms for incremental planarity testing (extended abstract)
• Mondshein sequences (a.k.a. (2,1)-orders)
• An effective crossing minimisation heuristic based on star insertion
• 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 linear-time algorithm for finding induced planar subgraphs
• 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
• A linear time algorithm for finding maximal planar subgraphs
• Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph
• A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks

This page was built for publication: A Linear-Time Algorithm for Finding a Maximal Planar Subgraph

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