Adding one edge to planar graphs makes crossing number hard

DOI10.1145/1810959.1810972zbMath1284.05070OpenAlexW2112380569MaRDI QIDQ5405864

Bojan Mohar, Sergio Cabello

Publication date: 3 April 2014

Published in: Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1810959.1810972

zbMATH Keywords

planar graphsNP-hardcrossing numbergraph drawinggraph embeddingtopological graph theory

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial complexity of geometric structures (52C45)

Related Items (4)

A note on 1-planar graphs ⋮ Hardness of approximation for crossing number ⋮ Vertex insertion approximates the crossing number of apex graphs ⋮ A tighter insertion-based approximation of the crossing number

This page was built for publication: Adding one edge to planar graphs makes crossing number hard