Thrackles: An improved upper bound

conference paper Thrackles: An improved upper bound LNCS published yes Radoslav Fulek author 39F3FFE4-F248-11E8-B48F-1D18A9856A870000-0001-8485-1774 János Pach author UlWa department GD: Graph Drawing and Network Visualization A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3/2(n-1), and that this bound is best possible for infinitely many values of n. Springer2018Boston, MA, United States eng 1708.0803710.1007/978-3-319-73915-1_14 10692160 - 166 https://research-explorer.ista.ac.at/record/5857 R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166. R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at the GD: Graph Drawing and Network Visualization, Boston, MA, United States, 2018, vol. 10692, pp. 160–166. Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166. Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer; 2018:160-166. doi:<a href="https://doi.org/10.1007/978-3-319-73915-1_14">10.1007/978-3-319-73915-1_14</a> Fulek, R., & Pach, J. (2018). Thrackles: An improved upper bound (Vol. 10692, pp. 160–166). Presented at the GD: Graph Drawing and Network Visualization, Boston, MA, United States: Springer. <a href="https://doi.org/10.1007/978-3-319-73915-1_14">https://doi.org/10.1007/978-3-319-73915-1_14</a> Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,” 10692:160–66. Springer, 2018. <a href="https://doi.org/10.1007/978-3-319-73915-1_14">https://doi.org/10.1007/978-3-319-73915-1_14</a>. Fulek, Radoslav, and János Pach. <i>Thrackles: An Improved Upper Bound</i>. Vol. 10692, Springer, 2018, pp. 160–66, doi:<a href="https://doi.org/10.1007/978-3-319-73915-1_14">10.1007/978-3-319-73915-1_14</a>. 4332018-12-11T11:46:27Z2026-04-16T09:48:11Z