Opuscula Mathematica
Opuscula Math. 46, no. 5 (2026), 679-707

Mutual-visibility of the disjointness graph of segments in R2

Jesús Leaños
Mario Lomelí-Haro
Christophe Ndjatchi
Luis Manuel Ríos-Castro
Abstract. 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.
Keywords: disjointness graph of segments, mutual-visibility, straight-line drawings of complete graphs.
Mathematics Subject Classification: 05C10, 05C12, 05C62.
Full text (pdf)
References ▼
  1. [1] O. Aichholzer, J. Kynčl, M. Scheucher, B. Vogtenhuber, On \(4\)-crossing-families in point sets and an asymptotic upper bound, [in:] Proceedings of the 37th European Workshop on Computational Geometry (EuroCG 2021), 2021, 38:1-38:8.
  2. [2] G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy, J. Urrutia, On the chromatic number of some geometric type Kneser graphs, Comput. Geom. 32 (2005), 59-69.
  3. [3] G. Boruzanlı Ekinci, C. Bujtás, Mutual-visibility problems in Kneser and Johnson graphs, Ars Math. Contemp. 25 (2025), #P3.07. https://doi.org/10.26493/1855-3974.3344.4c8
  4. [4] C. Bujtás, S. Klavžar, J. Tian, Total mutual-visibility in Hamming graphs, Opuscula Math. 45 (2025), 63-78. https://doi.org/10.7494/opmath.2025.45.1.63
  5. [5] S. Cicerone, G. Di Stefano, L. Drožđek, J. Hedžet, S. Klavžar, I.G. Yero, Variety of mutual-visibility problems in graphs, Theoret. Comput. Sci. 974 (2023), 114096. https://doi.org/10.1016/j.tcs.2023.114096
  6. [6] S. Cicerone, G. Di Stefano, S. Klavžar, On the mutual visibility in Cartesian products and triangle-free graphs, Appl. Math. Comput. 438 (2023), 127619. https://doi.org/10.1016/j.amc.2022.127619
  7. [7] S. Cicerone, G. Di Stefano, S. Klavžar, I.G. Yero, Mutual-visibility problems on graphs of diameter two, Eur. J. Combin. 120 (2024), 103995.
  8. [8] M. Dettlaff, M. Lemańska, J.A. Rodríguez-Velázquez, I.G. Yero, Mobile mutual-visibility sets in graphs, Ars Math. Contemp. 26 (2026), #P1.10. https://doi.org/10.26493/1855-3974.3410.9bc
  9. [9] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022), 126850. https://doi.org/10.1016/j.amc.2021.126850
  10. [10] P. Erdős, G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470.
  11. [11] A. Espinoza-Valdez, J. Leaños, C. Ndjatchi, L.M. Ríos-Castro, An upper bound asymptotically tight for the connectivity of the disjointness graph of segments in the plane, Symmetry 13 (2021), 1050.
  12. [12] R. Fabila-Monroy, D.R. Wood, The chromatic number of the convex segment disjointness graph, [in:] A. Márquez, P. Ramos, J. Urrutia (eds.), Computational Geometry (EGC 2011), Lecture Notes in Comput. Sci. 7579, Springer, Berlin, Heidelberg, 2012, 79-84. https://doi.org/10.1007/978-3-642-34191-5_7
  13. [13] R. Fabila-Monroy, C. Hidalgo-Toscano, J. Leaños, M. Lomelí-Haro, The chromatic number of the disjointness graph of the double chain, Discrete Math. Theor. Comput. Sci. 22 (2020), #11.
  14. [14] R. Fabila-Monroy, J. Jonsson, P. Valtr, D.R. Wood, The exact chromatic number of the convex segment disjointness graph, arXiv:1804.01057 (2018).
  15. [15] J.J. García-Davila, J. Leaños, M. Lomelí-Haro, L.M. Ríos-Castro, The maximum chromatic number of the disjointness graph of segments on \(n\)-point sets in the plane with \(n\leq16\), Bol. Soc. Mat. Mex. 30 (2024), 85. https://doi.org/10.1007/s40590-024-00654-z
  16. [16] M. Kneser, Aufgabe 360, Jahresber. Dtsch. Math.-Ver. 58 (1955), 27.
  17. [17] J. Leaños, C. Ndjatchi, L.M. Ríos-Castro, On the connectivity of the disjointness graph of segments of point sets in general position in the plane, Discrete Math. Theor. Comput. Sci. 24 (2022), #15.
  18. [18] J. Leaños, C. Ndjatchi, L.M. Ríos-Castro, Disjointness graphs of segments in \({\mathbb R}^2\) are almost all hamiltonian, Discrete Appl. Math. 342 (2024), 168-173.
  19. [19] L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), 319-324. https://doi.org/10.1016/0097-3165(78)90022-5
  20. [20] J. Pach, G. Tardos, G. Tóth, Disjointness graphs of segments, [in:] B. Aronov, M.J. Katz (eds.), 33rd International Symposium on Computational Geometry (SoCG 2017), Leibniz Int. Proc. Inform. (LIPIcs) 77 (2017), 59:1-59:15.
  21. [21] L.M. Ríos-Castro, Mutual visibility of graph D(P), Proposition 1.3, computer program, https://tinyurl.com/bdfa534b.
  22. [22] Wolfram Research, Inc., Mathematica, Version 12.0, Champaign, IL, 2019.
  23. [23] K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951), 301.
About the authors ▼
Jesús Leaños
Unidad Académica de Matemáticas, Universidad Autónoma de Zacatecas, Calzada Solidaridad y Paseo La Bufa, Col. Hidráulica, CP. 98060, Zacatecas, Zac., México
Mario Lomelí-Haro
https://orcid.org/0000-0003-3921-1369
Centro de Modelación Matemática, Vinculación y Consultoría, Universidad Tecnológica de la Mixteca, México
Christophe Ndjatchi (corresponding author)
https://orcid.org/0000-0003-2702-9981
Academia de Físico-Matemáticas, Instituto Politécnico Nacional, UPIIZ, P.C. 098160, Zacatecas, México
Luis Manuel Ríos-Castro
Academia de Físico-Matemáticas, Instituto Politécnico Nacional, CECYT18, P.C. 098160, Zacatecas, México
About the article ▼
Communicated by Andrzej Żak.
Received: 2025-06-25.
Revised: 2026-10-12.
Accepted: 2026-10-12.
Published online: 2026-10-28.
Cite this article as ▼
Jesús Leaños, Mario Lomelí-Haro, Christophe Ndjatchi, Luis Manuel Ríos-Castro, Mutual-visibility of the disjointness graph of segments in R2, Opuscula Math. 46, no. 5 (2026), 679-707, https://doi.org/10.7494/OpMath.202610122.
Download this article's citation as: