Premium
Maximal Rectilinear Crossing of Cycles
Author(s) -
Furry W. H.,
Kleitman D. J.
Publication year - 1977
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1002/sapm1977562159
Subject(s) - combinatorics , mathematics , crossing number (knot theory) , integer (computer science) , graph , wheel graph , plane (geometry) , discrete mathematics , geometry , line graph , computer science , graph power , intersection (aeronautics) , engineering , programming language , aerospace engineering
We address the following question: In drawing a cycle on n vertices (or a graph all of whose degrees are 2) in the plane with straight line arcs, how many crossings can there be? A complete answer is given; namely, if n is odd, the number of crossings can be anything up to n ( n −3)/2 except n ( n −3)/2−1. For n even, the number of crossings in one cycle can be any integer up to n ( n −4)/2+1; general bivalent even graphs can achieve any integer up to n (2 n −7)/4 as the number of crossings.