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 -