Maximal Rectilinear Crossing of Cycles
Maximal Rectilinear Crossing of Cycles
复制标题
循环的最大直线交叉
DOI：
--
复制
发表时间：
1977
期刊：
影响因子：
--
通讯作者：
D. Kleitman
中科院分区：
文献类型：
--
作者：
W. H. Furry;D. Kleitman
我们解决以下问题：在平面上用直线弧画一个n个顶点的圈（或一个度都是2的图），可以有多少个交点？给出了一个完整的答案;即，如果n是奇数，则交叉数可以是除n（n-3）/2 - 1之外的任何数，直到n（n-3）/2。对于n个偶数，一个圈中的交叉数可以是n（n−4）/2+1以内的任何整数;一般的二价偶数图可以达到n（2n−7）/4以内的任何整数作为交叉数。
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(2n−7)/4 as the number of crossings.