On the complexity of the approximation of nonplanarity parameters for cubic graphs

DOI10.1016/S0166-218X(03)00370-6zbMath1042.05092MaRDI QIDQ1827857

Candido F. X. Mendonça, Celina M. Herrera de Figueiredo, Luérbio Faria

Publication date: 6 August 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Complexity classesComputational difficulty of problemsMaximum planar subgraphSplitting numberTopological graph theory

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Approximation Algorithms for Euler Genus and Related Problems ⋮ Finding Triangles for Maximum Planar Subgraphs ⋮ On maximum planar induced subgraphs ⋮ Unnamed Item ⋮ Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs ⋮ Large planar subgraphs in dense graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Edge-Deletion Problems
• A Better Approximation Algorithm for Finding Planar Subgraphs
• SPLITTING NUMBER is NP-complete

This page was built for publication: On the complexity of the approximation of nonplanarity parameters for cubic graphs