Crossing number and weighted crossing number of near-planar graphs
From MaRDI portal
Publication:548655
DOI10.1007/s00453-009-9357-5zbMath1218.68083OpenAlexW2010561968MaRDI QIDQ548655
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
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