J. Leaños ; Christophe Ndjatchi ; L. M. RíosCastro

On the connectivity of the disjointness graph of segments of point sets
in general position in the plane
On the connectivity of the disjointness graph of segments of point sets
in general position in the plane
Authors: J. Leaños ; Christophe Ndjatchi ; L. M. RíosCastro
NULL##0000000327029981##NULL
J. Leaños;Christophe Ndjatchi;L. M. RíosCastro
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{n2}{2}\rfloor}{2}+\binom{\lceil\frac{n2}{2}\rceil}{2}$,
and that this bound is tight for each $n\geq 3$.