O(n2) algorithms for graph planarization

DOI10.1007/3-540-50728-0_56MaRDI QIDQ6199475zbMATH OpenFDO

Authors R. Jayakumar, Krishnaiyan Thulasiraman, M. N. S. Swamy

Publication date 28 February 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-50728-0_56

Mathematics Subject Classification ID

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

Recommendations

• On maximal planarization of nonplanar graphs
• A linear time algorithm for finding maximal planar subgraphs
• An analysis of heuristics for graph planarization
• A linear algorithm for the maximal planar subgraph problem
• An efficient graph planarization two‐phase heuristic

Cites work

• Computing an st-numbering
• Efficient Planarity Testing
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3716814 (Why is no real title available?)
• scientific article; zbMATH DE number 3585463 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• On maximal planarization of nonplanar graphs
• Planar embedding: linear-time algorithms for vertex placement and edge orderings
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

This page was built for publication: O(n2) algorithms for graph planarization

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