Vertex insertion approximates the crossing number of apex graphs

DOI10.1016/j.ejc.2011.09.009zbMath1230.05267OpenAlexW1982661321WikidataQ56977068 ScholiaQ56977068MaRDI QIDQ661940

Petr Hliněný, Markus Chimani, Petra Mutzel

Publication date: 11 February 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2011.09.009

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Inserting Multiple Edges into a Planar Graph ⋮ Exact crossing number parameterized by vertex cover ⋮ Crossing numbers and stress of random graphs ⋮ Crossing number for graphs with bounded pathwidth ⋮ A tighter insertion-based approximation of the crossing number ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Advances in the Planarization Method: Effective Multiple Edge Insertions ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ Unnamed Item ⋮ Kernelization of Whitney Switches ⋮ Kernelization of Whitney Switches ⋮ An effective crossing minimisation heuristic based on star insertion

Cites Work

• Crossing number and weighted crossing number of near-planar graphs
• The crossing number of a projective graph is quadratic in the face-width
• Inserting an edge into a planar graph
• A tighter insertion-based approximation of the crossing number
• Improved approximations of crossings in graph drawings
• Crossing Number is NP-Complete
• A New Approach to Exact Crossing Minimization
• On the Crossing Number of Almost Planar Graphs
• Approximating the Crossing Number of Toroidal Graphs
• Adding one edge to planar graphs makes crossing number hard
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Vertex insertion approximates the crossing number of apex graphs