Authors: J. Leaños ; Christophe Ndjatchi ; L. M. Ríos-Castro

Let $P$ be a set of $n\geq 3$ points in general position in the plane. The edge disjointness graph $D(P)$ of $P$ is the graph whose vertices are all the closed straight line segments with endpoints in $P$, two of which are adjacent in $D(P)$ if and only if they are disjoint. We show that the connectivity of $D(P)$ is at least $\binom{\lfloor\frac{n-2}{2}\rfloor}{2}+\binom{\lceil\frac{n-2}{2}\rceil}{2}$, and that this bound is tight for each $n\geq 3$.

Comment: 16 pages, 5 figures

• 05C40 - Connectivity
• 52C35 - Arrangements of points, flats, hyperplanes (aspects of discrete geometry)