On the connectivity of the disjointness graph of segments of point sets in general position in the plane

Abstract

Let $P$ be a set of $n\ge 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 $\left(\genfrac{}{}{0ex}{}{\lfloor \frac{n-2}{2}\rfloor }{2}\right)+\left(\genfrac{}{}{0ex}{}{\lceil \frac{n-2}{2}\rceil }{2}\right)$, and that this bound is tight for each $n\ge 3$.

16 pages, 5 figures

References in corpus (2)

• The exact chromatic number of the convex segment disjointness graph
• The Chromatic Number of the Disjointness Graph of the Double Chain