𝔖 Bobbio Scriptorium
✦   LIBER   ✦

New results on rectilinear crossing numbers and plane embeddings

✍ Scribed by Daniel Bienstock; Nathaniel Dean

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
561 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We show that if a graph has maximum degree d and crossing number k, its rectilinear crossing number is at most O(dk^2^). 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.

πŸ“œ SIMILAR VOLUMES

On a Crossing Number Result of Richter a
On a Crossing Number Result of Richter and Thomassen
✍ Gelasio Salazar πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 67 KB

We show that if G is a graph minimal with respect to having crossing number at least k, and G has no vertices of degree 3, then G has crossing number at most 2k+35. ## 2000 Academic Press Richter and Thomassen proved that if G is minimal with respect to having crossing number at least k, then the