Crossing and Weighted Crossing Number of Near-Planar Graphs

DOI10.1007/978-3-642-00219-9_5zbMath1213.68432OpenAlexW2129252388MaRDI QIDQ3611835

Bojan Mohar, Sergio Cabello

Publication date: 3 March 2009

Published in: Graph Drawing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00219-9_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (7)

Exact crossing number parameterized by vertex cover ⋮ A tighter insertion-based approximation of the crossing number ⋮ Strong embeddings of minimum genus ⋮ Approximating the Crossing Number of Apex Graphs ⋮ Advances in the Planarization Method: Effective Multiple Edge Insertions ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ A Linear-Time Algorithm for Finding Induced Planar Subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• A note on isoperimetric peaks of complete trees
• 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
• The Minor Crossing Number
• On the Crossing Number of Almost Planar Graphs
• New lower bound techniques for VLSI

This page was built for publication: Crossing and Weighted Crossing Number of Near-Planar Graphs