DOI: 10.7494/opmath.202610122 ISSN: 1232-9274

Mutual-visibility of the disjointness graph of segments in R<sup>2</sup>

Jesús Leaños, Mario Lomelí-Haro, Christophe Ndjatchi, Luis Manuel Ríos-Castro

Let \(G=(V(G),E(G))\) be a simple graph, and let \(U\subseteq V(G)\). Two distinct vertices \(x,y\in U\) are \(U\)-mutually visible if \(G\) contains a shortest \(x\)-\(y\) path that is internally disjoint from \(U\). \(U\) is called a mutual-visibility set of \(G\) if any two vertices of \(U\) are \(U\)-mutually visible. The mutual-visibility number \(\mu(G)\) of \(G\) is the size of a largest mutual-visibility set of \(G\). Let \(P\) be a set of \(n\geq 3\) points in \(\mathbb{R}^2\) in general position. The disjointness graph of segments \(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. In this paper we establish tight lower and upper bounds for \(\mu(D(P))\), and show that \(D(P)\) has diameter 2 for every point set with \(n\) at least 9.

More from our Archive