On the crossing number of complete graphs

被引：11

作者：

Aichholzer, O

Aurenhammer, F

Krasser, H

机构：

[1] Graz Univ Technol, Inst Software Technol, A-8010 Graz, Austria

[2] Graz Univ Technol, Inst Theoret Comp Sci, A-8010 Graz, Austria

来源：

COMPUTING | 2006年 / 76卷 / 1-2期

关键词：

crossing number; complete graph; order types; enumeration;

D O I：

10.1007/s00607-005-0133-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let (cr) over bar( G) denote the rectilinear crossing number of a graph G. We determine (cr) over bar (K-11) = 102 and (cr) over bar (K-12) = 153. Despite the remarkable hunt for crossing numbers of the complete graph K-n - initiated by R. Guy in the 1960s - these quantities have been unknown for n > 10 to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points ( order types) of size 11. Based on these findings, we establish a new upper bound on (cr) over bar (K-n) for general n. The bound stems from a novel construction of drawings of K-n with few crossings.

引用

页码：165 / 176

页数：12

共 27 条

[1] ABREGO B, IN PRESS GRAPHS COMB
[2] Enumerating order types for small point sets with applications
Aichholzer, O
Aurenhammer, F
Krasser, H
[J]. ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2002, 19 (03): : 265 - 281
[3] AICHHOLZER O, 2001, P 13 CAN C COMP GEOM, P17
[4] AICHHOLZER O, 2002, P 18 ANN ACM S COMP, P19
[5] Aichholzer Oswin, 2005, P 21 S COMP GEOM, P91
[6] BALOGH J, UNPUB K SETS CONVEX
[7] SOME PROVABLY HARD CROSSING NUMBER PROBLEMS
BIENSTOCK, D
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) : 443 - 459
[8] Toward the rectilinear crossing number of Kn:: new drawings, upper bounds, and asymptotics
Brodsky, A
Durocher, S
Gethner, E
[J]. DISCRETE MATHEMATICS, 2003, 262 (1-3) : 59 - 77
[9] BRODSKY A, 2001, ELECT J COMBINATORIC, V8
[10] ERDOS P, 1973, AM MATH MONTHLY, V88, P52

← 1 2 3 →