Approximating the Crossing Number of Toroidal Graphs

DOI10.1007/978-3-540-77120-3_15MaRDI QIDQ5387753zbMATHOpenAlexFDO

Authors 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

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

Recommendations

• Approximating the crossing number of graphs embeddable in any orientable surface
• An algorithm for the graph crossing number problem
• scientific article; zbMATH DE number 5130834
• Graph Drawing
• On the Crossing Number of Almost Planar Graphs

Cites work

• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 5506235 (Why is no real title available?)
• scientific article; zbMATH DE number 881174 (Why is no real title available?)
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree
• Computing crossing numbers in quadratic time
• Crossing Number is NP-Complete
• Crossing number is hard for cubic graphs
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Graph Drawing
• Graphs on surfaces
• Grid minors of graphs on the torus
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• On the Crossing Number of Almost Planar Graphs
• On the crossing number of almost planar graphs
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
• Planar Crossing Numbers of Genus g Graphs
• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• The Minor Crossing Number
• The crossing number of a projective graph is quadratic in the face–width
• The minor crossing number of graphs with an excluded minor

Cited in

(12)

• scientific article; zbMATH DE number 7278018 (Why is no real title available?)
• Graph Drawing
• scientific article; zbMATH DE number 4155924 (Why is no real title available?)
• Approximating the crossing number of graphs embeddable in any orientable surface
• Crossing numbers and stress of random graphs
• Crossing number for graphs with bounded pathwidth
• Toroidal grid minors and stretch in embedded graphs
• Polyhedral suspensions of arbitrary genus
• On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle
• Vertex insertion approximates the crossing number of apex graphs
• scientific article; zbMATH DE number 5130834 (Why is no real title available?)
• On enumeration of a class of toroidal graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387753)