TY - GEN

T1 - On conway's thrackle conjecture

AU - Lovász, László

AU - Pach, János

AU - Szegedy, Mario

N1 - Funding Information:
by NSF grant CCR-94-02916. by NSF grant CCR-91-22103, 663472 and OTKA-4269.
Publisher Copyright:
© 1995 ACM.

PY - 1995/9/1

Y1 - 1995/9/1

N2 - A thrackle is a graph that can be 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 thirty 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.

AB - A thrackle is a graph that can be 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 thirty 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.

UR - http://www.scopus.com/inward/record.url?scp=26144449752&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26144449752&partnerID=8YFLogxK

U2 - 10.1145/220279.220295

DO - 10.1145/220279.220295

M3 - Conference contribution

AN - SCOPUS:26144449752

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 147

EP - 151

BT - Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995

PB - Association for Computing Machinery

T2 - 11th Annual Symposium on Computational Geometry, SCG 1995

Y2 - 5 June 1995 through 7 June 1995

ER -