Crossing number and weighted crossing number of near-planar graphs

DOI10.1007/S00453-009-9357-5zbMATH Open1218.68083OpenAlexW2010561968MaRDI QIDQ548655FDOQ548655

S. 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

Recommendations

• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Adding one edge to planar graphs makes crossing number hard
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• On the Crossing Number of Almost Planar Graphs
• On graph crossing number and edge planarization

zbMATH Keywords

NP-hardnesscrossing numberdual distancealmost planarfacial distancenear-planarplanar separation

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Additive combinatorics
• Graphs on surfaces
• On the number of sums and products
• ON THE NUMBER OF SUMS AND PRODUCTS
• Crossing Number is NP-Complete
• Dividing a Graph into Triconnected Components
• A framework for solving VLSI graph layout problems
• Elimination of local bridges
• Planarizing graphs---a survey and annotated bibliography
• Title not available (Why is that?)
• Separation of vertices by a circuit
• Title not available (Why is that?)
• A linear-time algorithm for finding an ambitus
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Inserting an edge into a planar graph
• On the crossing number of almost planar graphs
• On the Crossing Number of Almost Planar Graphs

Cited In (16)

• Crossing number for graphs with bounded pathwidth
• Crossing numbers and stress of random graphs
• Toroidal grid minors and stretch in embedded graphs
• Crossing numbers of beyond-planar graphs
• A tighter insertion-based approximation of the crossing number
• Strong embeddings of minimum genus
• Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
• Star-struck by fixed embeddings: modern crossing number heuristics
• Excluded minors for the Klein bottle. II: Cascades
• Inserting Multiple Edges into a Planar Graph
• Parameterized analysis and crossing minimization problems
• An effective crossing minimisation heuristic based on star insertion
• Title not available (Why is that?)
• On the Crossing Number of Almost Planar Graphs
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Vertex insertion approximates the crossing number of apex graphs

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

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