Crossing number and weighted crossing number of near-planar graphs

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

Sergio Cabello, Bojan Mohar

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 numberNP-hardnessdual distancealmost planarfacial distancenear-planarplanar separation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics ⋮ Star-struck by fixed embeddings: modern crossing number heuristics ⋮ Parameterized analysis and crossing minimization problems ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Excluded minors for the Klein bottle. II: Cascades ⋮ Crossing numbers and stress of random graphs ⋮ Vertex insertion approximates the crossing number of apex graphs ⋮ Crossing number for graphs with bounded pathwidth ⋮ A tighter insertion-based approximation of the crossing number ⋮ Strong embeddings of minimum genus ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Unnamed Item ⋮ An effective crossing minimisation heuristic based on star insertion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• A linear-time algorithm for finding an ambitus
• Separation of vertices by a circuit
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Inserting an edge into a planar graph
• Planarizing Graphs - A Survey and Annotated Bibliography
• Crossing Number is NP-Complete
• On the Crossing Number of Almost Planar Graphs
• On the number of sums and products
• Dividing a Graph into Triconnected Components
• ON THE NUMBER OF SUMS AND PRODUCTS

This page was built for publication: Crossing number and weighted crossing number of near-planar graphs