Planar crossing numbers of graphs of bounded genus

DOI10.1007/s00454-012-9430-8zbMath1248.05044MaRDI QIDQ452001

Hristo N. Djidjev, Imrich Vrt'o

Publication date: 19 September 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9430-8

zbMATH Keywords

crossing number; genus; orientable surface; surface crossing number

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

57M15: Relations of low-dimensional topology with graph theory

Related Items

Toroidal grid minors and stretch in embedded graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improving the crossing lemma by finding more crossings in sparse graphs
• Edge separators for graphs of bounded genus with applications
• Partitioning planar graphs with vertex costs: Algorithms and applications
• Algorithms for the fixed linear crossing number problem
• Computing crossing numbers in quadratic time
• Applications of the crossing number
• Crossing number is hard for cubic graphs
• Planarizing Graphs - A Survey and Annotated Bibliography
• [https://portal.mardi4nfdi.de/wiki/Publication:3156923 The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)]
• Crossing Number is NP-Complete
• A New Approach to Exact Crossing Minimization
• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Planar Crossing Numbers of Genus g Graphs
• Crossing-Free Subgraphs
• On VLSI layouts of the star graph and related networks
• Crossing Numbers and Cutwidths
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• An algorithm for the graph crossing number problem
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
• On a problem of P. Turan concerning graphs
• Graph Drawing