On the edge-vertex ratio of maximal thrackles

DOI10.1007/978-3-030-35802-0_37arXiv1908.08857MaRDI QIDQ6324092FDOQ6324092

Felix Schröder, Linda Kleist, Boris Klemz, Birgit Vogtenhuber, Oswin Aichholzer

Publication date: 23 August 2019

Abstract: A drawing of a graph in the plane is a thrackle if every pair of edges intersects exactly once, either at a common vertex or at a proper crossing. Conway's conjecture states that a thrackle has at most as many edges as vertices. In this paper, we investigate the edge-vertex ratio of maximal thrackles, that is, thrackles in which no edge between already existing vertices can be inserted such that the resulting drawing remains a thrackle. For maximal geometric and topological thrackles, we show that the edge-vertex ratio can be arbitrarily small. When forbidding isolated vertices, the edge-vertex ratio of maximal geometric thrackles can be arbitrarily close to the natural lower bound of 1/2. For maximal topological thrackles without isolated vertices, we present an infinite family with an edge-vertex ratio of 5/6.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

This page was built for publication: On the edge-vertex ratio of maximal thrackles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324092)