Approximating the Crossing Number of Toroidal Graphs

DOI10.1007/978-3-540-77120-3_15zbMath1193.05116OpenAlexW1549500393MaRDI QIDQ5387753

Petr Hliněný, Gelasio Salazar

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_15

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (7)

Polyhedral suspensions of arbitrary genus ⋮ 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 ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• The minor crossing number of graphs with an excluded minor
• Grid minors of graphs on the torus
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• Computing crossing numbers in quadratic time
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• The Minor Crossing Number
• The crossing number of a projective graph is quadratic in the face–width
• On the Crossing Number of Almost Planar Graphs
• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Planar Crossing Numbers of Genus g Graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
• Graph Drawing

This page was built for publication: Approximating the Crossing Number of Toroidal Graphs