简单平面图中短圈数目的估计

Estimating the number of short cycles in simple planar graphs

证明一个n阶简单2-连通平面图G中至多有O(n^2)个最短圈(即存在绝对常数c>0使得G中至多有cn^2个最短圈),且该界就n的量级来讲是最好可能的,K_(n-2,2)表明了n^2是可以达到的量级.

This paper showed that the number of the shortest cycles in a planar graph of order n is at most O（n2） and the bound is the best possible （subject to the power of n） since Kn-2,n contains exactly （n-2）（n-3）/2 many 4-cycles.