New results on rectilinear crossing numbers and plane embeddings
Daniel A. Bienstock, Nathaniel Dean · Journal of Graph Theory · 1992
Abstract We show that if a graph has maximum degree d and crossing number k, its rectilinear crossing number is at most O(dk2). Hence for graphs of bounded degree, the crossing number and the rectilinear crossing number are bounded as functions of one another. We also obtain a generalization of Tutte's theorem on convex embeddings of 3‐connected plane graphs. © 1929 John Wiley & Sons, Inc.