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

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

doi:10.46298/dmtcs.6678

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

J. Leaños, Christophe Ndjatchi, L. M. Ríos-Castro

Unidad Profesional Interdisciplinaria de Ingeniería, Campus Zacatecas (UPIIZ)

Research output: Contribution to journal › Article › peer-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 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 ^(bn−₂^{2 2 c)} + ^(dn−₂^{2 2 e)}, and that this bound is tight for each n ≥ 3.

Original language	English
Article number	5
Journal	Discrete Mathematics and Theoretical Computer Science
Volume	24
Issue number	1
DOIs	https://doi.org/10.46298/dmtcs.6678
State	Published - 2022

Keywords

Connectivity
Crossings of segments
Disjointness graph of segments
Menger’s theorem

Access to Document

10.46298/dmtcs.6678

Cite this

@article{58753913209e4549b132930e0bf44102,

title = "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 ≥ 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 (bn−22 2 c) + (dn−22 2 e), and that this bound is tight for each n ≥ 3.",

keywords = "Connectivity, Crossings of segments, Disjointness graph of segments, Menger{\textquoteright}s theorem",

author = "J. Lea{\~n}os and Christophe Ndjatchi and R{\'i}os-Castro, {L. M.}",

note = "Publisher Copyright: {\textcopyright} 2022 by the author(s)",

year = "2022",

doi = "10.46298/dmtcs.6678",

language = "Ingl{\'e}s",

volume = "24",

journal = "Discrete Mathematics and Theoretical Computer Science",

issn = "1462-7264",

number = "1",

}

TY - JOUR

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

AU - Leaños, J.

AU - Ndjatchi, Christophe

AU - Ríos-Castro, L. M.

PY - 2022

Y1 - 2022

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 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 (bn−22 2 c) + (dn−22 2 e), and that this bound is tight for each n ≥ 3.

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 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 (bn−22 2 c) + (dn−22 2 e), and that this bound is tight for each n ≥ 3.

KW - Connectivity

KW - Crossings of segments

KW - Disjointness graph of segments

KW - Menger’s theorem

UR - http://www.scopus.com/inward/record.url?scp=85132421787&partnerID=8YFLogxK

U2 - 10.46298/dmtcs.6678

DO - 10.46298/dmtcs.6678

M3 - Artículo

AN - SCOPUS:85132421787

SN - 1462-7264

VL - 24

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

IS - 1

M1 - 5

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this