Planar crossing numbers of graphs of bounded genus

DOI10.1007/S00454-012-9430-8MaRDI QIDQ452001zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Planar Crossing Numbers of Genus g Graphs
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
• scientific article; zbMATH DE number 5130834
• Graph Drawing
• Genus, treewidth, and local crossing number

Cites work

• A New Approach to Exact Crossing Minimization
• Algorithms for the fixed linear crossing number problem
• An algorithm for the graph crossing number problem
• Applications of the crossing number
• Computing crossing numbers in quadratic time
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• Crossing Numbers and Cutwidths
• Crossing-Free Subgraphs
• Edge separators for graphs of bounded genus with applications
• Graph Drawing
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 1054768 (Why is no real title available?)
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Improving the crossing lemma by finding more crossings in sparse graphs
• On a problem of P. Turan concerning graphs
• On VLSI layouts of the star graph and related networks
• Partitioning planar graphs with vertex costs: Algorithms and applications
• Planar Crossing Numbers of Genus g Graphs
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Planarizing graphs---a survey and annotated bibliography
• Survey of the crossing number of graphs
• The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)

Cited in

(19)

• The crossing number of a projective graph is quadratic in the face-width
• New bounds on crossing numbers
• Drawings of graphs on surfaces with few crossings
• Toroidal grid minors and stretch in embedded graphs
• Planar decompositions and the crossing number of graphs with an excluded minor
• Genus, treewidth, and local crossing number
• The crossing number of a projective graph is quadratic in the face–width
• The genus crossing number
• Planar Crossing Numbers of Genus g Graphs
• The degenerate crossing number and higher-genus embeddings
• Polylogarithmic approximation for Euler genus on bounded degree graphs
• Structure of graphs with locally restricted crossings
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
• Graph Drawing
• Crossing numbers of beyond-planar graphs
• Improved product structure for graphs on surfaces
• Planarization of graphs embedded on surfaces
• Improved bounds for the crossing numbers on surfaces of genus g
• Rectilinear crossing number of graphs excluding a single-crossing graph as a minor

This page was built for publication: Planar crossing numbers of graphs of bounded genus

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