A Linear-Time Algorithm for Finding a Maximal Planar Subgraph

DOI10.1137/S0895480197328771zbMath1118.05089OpenAlexW2100261054MaRDI QIDQ3440266

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

planar graphsdata structurestriconnectivityincremental algorithmsplanarity testinggraph planarization

Mathematics Subject Classification ID

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

Related Items (6)

Edge-orders ⋮ A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ The spanning maximal planar subgraph problem for some classes of complete 4-partite graphs ⋮ An effective crossing minimisation heuristic based on star insertion

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