Bounds for rectilinear crossing numbers

DOI10.1002/JGT.3190170308MaRDI QIDQ4201390zbMATH OpenOpenAlexFDO

Authors Daniel Bienstock, Nathaniel Dean

Publication date 24 August 1993

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.3190170308

zbMATH Keywords

crossing numberrectilinear crossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Recommendations

• A lower bound for the rectilinear crossing number
• Note on \(k\)-planar crossing numbers
• New results on rectilinear crossing numbers and plane embeddings
• The rectilinear local crossing number of \(K_{n}\)
• On the crossing number of complete graphs

Cited in

(48)

• Some provably hard crossing number problems
• Upper bounds for ropelength as a function of crossing number.
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Note on \(k\)-planar crossing numbers
• Which crossing number is it anyway?
• Applications of the crossing number
• On the degenerate crossing number
• Parameterized analysis and crossing minimization problems
• On the 2-colored crossing number
• Weighted Turán problems with applications
• Approximating the rectilinear crossing number
• Two recursive inequalities for crossing numbers of graphs
• The early history of the brick factory problem
• Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length
• A better bound for the pair-crossing number
• The minimum of the maximum rectilinear crossing numbers of small cubic graphs
• Space crossing numbers
• Approximating the rectilinear crossing number
• On the Pseudolinear Crossing Number
• Bounds for Convex Crossing Numbers
• Hanani-Tutte and monotone drawings
• The maximum rectlinear crossing number of generalized wheel graphs
• On the crossing number of honeycomb related networks
• Monotone Crossing Number
• The Orchard crossing number of an abstract graph
• The Crossing Number of Graphs: Theory and Computation
• scientific article; zbMATH DE number 3954950 (Why is no real title available?)
• New results on rectilinear crossing numbers and plane embeddings
• scientific article; zbMATH DE number 1054768 (Why is no real title available?)
• Crossing properties of graph reliability functions
• Maximum rectilinear crossing numbers of polyomino graphs
• Crossing numbers of random graphs
• On the crossing number for Kronecker product of a tripartite graph with path
• Limiting Crossing Numbers for Geodesic Drawings on the Sphere
• Crossing Numbers of Beyond-Planar Graphs Revisited
• An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Rectilinear crossing number of a zero divisor graph
• On the minimum of the maximum rectilinear crossing numbers of regular graphs
• Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
• Reviews
• A note on the maximum rectilinear crossing number of spiders
• Approximating the crossing number of dense graphs (poster abstract)
• Rectilinear crossing number of graphs excluding a single-crossing graph as a minor
• The complexity of tensor rank
• An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers
• A dichotomy for 1-planarity with restricted crossing types parameterized by treewidth
• Removing even crossings

This page was built for publication: Bounds for rectilinear crossing numbers

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