Approximating the Crossing Number of Toroidal Graphs

DOI10.1007/978-3-540-77120-3_15zbMATH Open1193.05116OpenAlexW1549500393MaRDI QIDQ5387753FDOQ5387753

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

Recommendations

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

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)

Cites Work

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

Cited In (13)

• Crossing number for graphs with bounded pathwidth
• On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle
• Crossing numbers and stress of random graphs
• Toroidal grid minors and stretch in embedded graphs
• Approximating the crossing number of graphs embeddable in any orientable surface
• A tighter insertion-based approximation of the crossing number
• Title not available (Why is that?)
• Graph Drawing
• Polyhedral suspensions of arbitrary genus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertex insertion approximates the crossing number of apex graphs
• 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)