Premium
New results on rectilinear crossing numbers and plane embeddings
Author(s) -
Bienstock Daniel,
Dean Nathaniel
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160502
Subject(s) - combinatorics , mathematics , crossing number (knot theory) , bounded function , regular polygon , plane (geometry) , planar graph , generalization , degree (music) , graph , discrete mathematics , geometry , mathematical analysis , physics , intersection (aeronautics) , acoustics , engineering , aerospace engineering
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.