On Conway's thrackle conjecture

被引：40

作者：

Lovasz, L

Pach, J

Szegedy, M

机构：

[1] CUNY CITY COLL,DEPT COMP SCI,NEW YORK,NY 10012

[2] NYU,COURANT INST,NEW YORK,NY 10012

[3] AT&T BELL LABS,MATH SCI RES CTR,MURRAY HILL,NJ 07974

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1997年 / 18卷 / 04期

关键词：

Related Problem; Point Interior; Common Vertex;

D O I：

10.1007/PL00009322

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs. About 40 years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices. We show that a thrackle has at most twice as many edges as vertices. Some related problems and generalizations are also considered.

引用

页码：369 / 376

页数：8

共 21 条

[1]

BABAI L, 1988, LINEAR ALGEBRA MET 1

[2]

BERLEKAMP ER, 1969, CANAD MATH B, V12, P363

[3]

DEBRUIJN NG, 1948, NEDERL AKAD WETENSCH, V51, P1277

[4]

DELOERA JA, IN PRESS COMBINATORI

[5] ALGORITHMS FOR DRAWING GRAPHS - AN ANNOTATED-BIBLIOGRAPHY [J].

DIBATTISTA, G ;

EADES, P ;

TAMASSIA, R ;

TOLLIS, IG .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1994, 4 (05) :235-282

[6] CROSSING NUMBER IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (03) :312-316

[7]

GRAHAM RL, 1975, J COMB THEORY A, V18, P165, DOI 10.1016/0097-3165(75)90004-7

[8]

GREENCOTTINGHAM J, 1993, THESIS CLEMSON U

[9]

Guy R. K., 1972, LECT NOTES MATH, V303, P111, DOI DOI 10.1007/BFB0067363

[10]

HOPF H, 1934, DTSCH MATH VEREIN, V43, P114

← 1 2 3 →