TY - JOUR
T1 - An upper bound asymptotically tight for the connectivity of the disjointness graph of segments in the plane
AU - Espinoza-Valdez, Aurora
AU - Leaños, Jesús
AU - Ndjatchi, Christophe
AU - Ríos-Castro, Luis Manuel
N1 - Publisher Copyright:
© 2021 by the authors. Licensee MDPI, Basel, Switzerland.
PY - 2021/6
Y1 - 2021/6
N2 - Let P be a set of n ≥ 3 points in general position in the plane. The edge disjointness graph D(P) of P is the graph whose vertices are the (n 2) closed straight line segments with endpoints in P, two of which are adjacent in D(P) if and only if they are disjoint. In this paper we show that the connectivity of D(P) is at most 7n2/18 + Θ(n), and that this upper bound is asymptotically tight. The proof is based on the analysis of the connectivity of D(Qn), where Qn denotes an n-point set that is almost 3-symmetric.
AB - Let P be a set of n ≥ 3 points in general position in the plane. The edge disjointness graph D(P) of P is the graph whose vertices are the (n 2) closed straight line segments with endpoints in P, two of which are adjacent in D(P) if and only if they are disjoint. In this paper we show that the connectivity of D(P) is at most 7n2/18 + Θ(n), and that this upper bound is asymptotically tight. The proof is based on the analysis of the connectivity of D(Qn), where Qn denotes an n-point set that is almost 3-symmetric.
KW - 3-symmetry
KW - Disjointness graph of segments
KW - Hall’s theorem
KW - Menger’s theorem
KW - Rectilinear local crossing number
UR - http://www.scopus.com/inward/record.url?scp=85109602498&partnerID=8YFLogxK
U2 - 10.3390/sym13061050
DO - 10.3390/sym13061050
M3 - Artículo
AN - SCOPUS:85109602498
SN - 2073-8994
VL - 13
JO - Symmetry
JF - Symmetry
IS - 6
M1 - 1050
ER -