On k-planar crossing numbers

DOI10.1016/J.DAM.2005.12.011zbMATH Open1121.05039OpenAlexW1970611748MaRDI QIDQ885282FDOQ885282

Authors: Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, Imrich Vrt'o 

Publication date: 8 June 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.12.011

Recommendations

• Graph Drawing
• Using block designs in crossing number bounds
• Note on \(k\)-planar crossing numbers
• The crossing number of 2-planar graphs and its application
• Computational search of small point sets with small rectilinear crossing number
• On the Decay of Crossing Numbers
• Computing crossing numbers in quadratic time
• Computing crossing numbers in quadratic time
• Crossing number, pair-crossing number, and expansion

zbMATH Keywords

lower boundcomplete graphcomplete bipartite graphcrossing number\(k\)-planar crossing numberrectilinear \(k\)-planar crossing number

Mathematics Subject Classification ID

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

Cites Work

• Edge-Disjoint Spanning Trees of Finite Graphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• Title not available (Why is that?)
• The crossing number of K5,n
• Title not available (Why is that?)
• Geometric Thickness of Complete Graphs
• Multilayer grid embeddings for VLSI
• Title not available (Why is that?)
• The toroidal crossing number of the complete graph
• Decompositions of graphs into forests with bounded maximum degree
• Title not available (Why is that?)
• The book crossing number of a graph
• Biplanar crossing numbers. I: A survey of results and problems

Cited In (21)

• On the 2-colored crossing number
• On the \(k\)-planar local crossing number
• Improved bounds for the crossing numbers on surfaces of genus g
• A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
• Book drawings of complete bipartite graphs
• Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
• Book embeddings and crossing numbers
• New bounds on the biplanar crossing number of low-dimensional hypercubes: how low can you go?
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Graph Drawing
• Using block designs in crossing number bounds
• Gap-planar graphs
• \(k\)-planar crossing number of random graphs and random regular graphs
• Note on \(k\)-planar crossing numbers
• Parameterized analysis and crossing minimization problems
• Title not available (Why is that?)
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• The crossing number of 2-planar graphs and its application
• \(k\)-planar graphs
• ON THE SATELLITE CROSSING NUMBER CONJECTURE
• Title not available (Why is that?)

This page was built for publication: On \(k\)-planar crossing numbers

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