On the Crossing Number of Almost Planar Graphs

DOI10.1007/978-3-540-70904-6_17zbMath1185.68485OpenAlexW1547288376MaRDI QIDQ3595462

Petr Hliněný, Gelasio Salazar

Publication date: 28 August 2007

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

Full work available at URL: https://doi.org/10.1007/978-3-540-70904-6_17

zbMATH Keywords

crossing numbercrossing minimizationplanarizationcrossing-critical graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Analogies between the crossing number and the tangle crossing number ⋮ Parameterized analysis and crossing minimization problems ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Characterizing planar tanglegram layouts and applications to edge insertion problems ⋮ Exact crossing number parameterized by vertex cover ⋮ Approximating the Crossing Number of Toroidal Graphs ⋮ Vertex insertion approximates the crossing number of apex graphs ⋮ Crossing number and weighted crossing number of near-planar graphs ⋮ A tighter insertion-based approximation of the crossing number ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Crossing and Weighted Crossing Number of Near-Planar Graphs ⋮ Approximating the Crossing Number of Apex Graphs ⋮ Advances in the Planarization Method: Effective Multiple Edge Insertions ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ An effective crossing minimisation heuristic based on star insertion ⋮ A Linear-Time Algorithm for Finding Induced Planar Subgraphs

This page was built for publication: On the Crossing Number of Almost Planar Graphs