Crossing number and weighted crossing number of near-planar graphs

DOI10.1007/s00453-009-9357-5zbMath1218.68083MaRDI QIDQ548655

Bojan Mohar, Sergio Cabello

Publication date: 30 June 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9357-5

zbMATH Keywords

crossing number; NP-hardness; dual distance; almost planar; facial distance; near-planar; planar separation

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C62: Graph representations (geometric and intersection representations, etc.)