Planar crossing numbers of graphs of bounded genus

DOI10.1007/s00454-012-9430-8zbMath1248.05044OpenAlexW2041021602MaRDI 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 numbergenusorientable surfacesurface crossing number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

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