Crossing number and weighted crossing number of near-planar graphs

DOI10.1007/S00453-009-9357-5MaRDI QIDQ548655zbMATH OpenOpenAlexFDO

Authors 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

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)

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

Cites work

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

Cited in

(17)

• Crossing number for graphs with bounded pathwidth
• Crossing numbers and stress of random graphs
• Adding one edge to planar graphs makes crossing number hard
• Toroidal grid minors and stretch in embedded graphs
• Crossing numbers of beyond-planar graphs
• 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
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Inserting Multiple Edges into a Planar Graph
• Parameterized analysis and crossing minimization problems
• An effective crossing minimisation heuristic based on star insertion
• scientific article; zbMATH DE number 7278018 (Why is no real title available?)
• 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)