An upper bound asymptotically tight for the connectivity of the disjointness graph of segments in the plane

Aurora Espinoza-Valdez, Jesús Leaños, Christophe Ndjatchi, Luis Manuel Ríos-Castro

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Article number1050
JournalSymmetry
Volume13
Issue number6
DOIs
StatePublished - Jun 2021

Keywords

  • 3-symmetry
  • Disjointness graph of segments
  • Hall’s theorem
  • Menger’s theorem
  • Rectilinear local crossing number

Fingerprint

Dive into the research topics of 'An upper bound asymptotically tight for the connectivity of the disjointness graph of segments in the plane'. Together they form a unique fingerprint.

Cite this