Pith. sign in

REVIEW 3 major objections 4 minor 23 references

Mutual-visibility of the disjointness graph of segments in ${\mathbb R}^2$

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For any n-point set in general position, the mutual-visibility number of its segment disjointness graph lies between C(n,2)-9 and C(n,2)-4, and the paper proves both extremes are attained.

desk verdict First real computation of mutual-visibility for segment disjointness graphs, with plausible asymptotics, but the n=7 lower-bound case rests on an unproved good-triangle assertion that a referee should see closed. read the letter →

arxiv 2506.00689 v2 pith:FNQNK7K7 submitted 2025-05-31 math.CO

J. Leaños , M. Lomelí-Haro , Christophe Ndjatchi , L. M. Ríos-Castro This is my paper
classification math.CO MSC 05C1005C1205C62
keywords mutualvisibilitydisjointnessgraphofsegmentsrectilineardrawingscompletegraphsdiametergeometricgeneralpositionpointsetsconvexdoublechainErdős–Szekerestheorem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies the mutual-visibility number of the disjointness graph D(P) of all segments determined by an n-point set P in general position in the plane. It establishes that, for n≥5, at least C(n,2)-9 of the segments can always be placed in a single mutual-visibility set, and that for large n this number is between C(n,2)-5 and C(n,2)-4. Both endpoint values are shown to be attainable: convex point sets give C(n,2)-5, and double chains give C(n,2)-4. The paper also proves that the diameter of D(P) is 2 once n≥9, so nearly all such graphs have diameter 2. The interest is that a geometric graph parameter, which is hard to compute in general, is here determined up to a small additive constant for every point configuration.

What carries the argument

The load-bearing tool is Lemma 7, the S-pair lemma: if one removes a small set S of segments and every remaining pair of crossing segments admits a shortest path whose internal vertices lie in S, then μ(D(P)) ≥ total - |S|. The proof then works by bounding |bP|, the number of points on the convex hull, and constructing such an S with |S| ≤ 9 using geometric gadgets: five pairwise disjoint clean segments, a 'good-triangle' whose sides are crossed only by a short list of segments, a 'good-2-set' formed by two disjoint clean segments plus two separating segments, and the Erdős–Szekeres theorem to find a large convex subset for the asymptotic lower bound. Clean segments, those crossed by no other segment, act as safe witnesses that certify visibility between otherwise-crossing pairs.

What would settle it

Take a 7-point set with six hull points v_1,…,v_6 and one interior point x. For each i, test condition (ii) of Definition 14 on both triangles x v_i v_{i+1} and x v_{i+3}v_{i+4}: find a segment uv whose endpoints lie outside the triangle, that intersects all three sides, and that is not one of the four listed exceptions v_i v_{i+2}, v_i v_{i+3}, v_{i+1} v_{i+4}, v_{i+1} v_{i+5}. If such a configuration exists, Lemma 19 Case 2 collapses; a direct computation of μ(D(P)) for that order type would then settle whether the theorem's lower bound still holds.

Watch

Extended reading notes

Core claim

The central claim is that the mutual-visibility number of the segment disjointness graph is asymptotically pinned down: for every n-point set P in general position, μ(D(P)) ≥ C(n,2)-9, and for n sufficiently large, C(n,2)-5 ≤ μ(D(P)) ≤ C(n,2)-4. A specific 7-point example shows the universal lower bound is sharp, while the upper bound C(n,2)-4 and the lower bound C(n,2)-5 are both attained, respectively by double chains and by point sets in convex position. An auxiliary theorem determines the diameter of D(P): it is 2 for n≥9, at most 3 for n in {6,7,8}, and at most 4 for n=5. In other words, almost all of the roughly $n^{2}$/2 segments can be chosen so that every pair is joined by a shortest path avoiding the other chosen segments.

Load-bearing premise

The proof of the six-hull-point case assumes without displaying the verification that, for a 7-point set with one interior point x, one of the triangles x v_i v_{i+1} or x v_{i+3} v_{i+4} is always a good-triangle; if this geometric check fails for every i, the universal bound μ(D(P)) ≥ C(7,2)-9 would not follow from the proof as written.

Editorial extensions

If this is right

  • For n≥9, D(P) has diameter exactly 2, so every pair of disjoint segments has a common neighbor and every pair of crossing segments is at distance 2 or 3.
  • The mutual-visibility number is C(n,2)-O(1): one can always exhibit a mutual-visibility set containing all but a constant number of the segments.
  • Convex point sets realize the lower end C(n,2)-5 and double chains realize the upper end C(n,2)-4, so neither asymptotic bound can be improved without excluding configurations.
  • The universal lower bound C(n,2)-9 is best possible at n=7, where a specific 7-point set has μ=12, showing that the bound is attained at least once.
  • For n≥9 the diameter theorem forces μ(D(P)) to be near-complete, because any missing visibility between two chosen segments must be certified through the small deleted set S.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The five-unit gap between the universal lower bound and the large-n upper bound suggests the exact asymptotic value is C(n,2)-5 or C(n,2)-4, with the choice likely governed by whether the point set contains five pairwise disjoint clean segments; convex sets and double chains are the two extremes.
  • The S-pair deletion technique is not specific to disjointness graphs: any graph whose distance structure is controlled by a small set of 'blocking' vertices admits the same kind of near-complete mutual-visibility certificate, so the method may transfer to other geometric intersection graphs.
  • Since the sharp example for C(n,2)-9 occurs only at n=7, the universal bound may be improvable for larger n; testing random point configurations with |bP|=6 or 7 for n>7 could reveal whether the true lower bound grows closer to C(n,2)-5.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the mutual-visibility number mu(D(P)) of the disjointness graph D(P) whose vertices are the segments determined by an n-point set P in general position. The main results are: a diameter theorem (diam(D(P)) is at most 2 for n>=9, at most 3 for n=6,7,8, and at most 4 for n=5); a universal lower bound mu(D(P)) >= C(n,2)-9; a computer-assisted 7-point example attaining equality; and asymptotic bounds C(n,2)-5 <= mu(D(P)) <= C(n,2)-4 for large n, with convex point sets attaining the lower bound and double chains attaining the upper bound. The proof machinery consists of constructing small sets S of excluded segments such that P\S is a mutual-visibility set, using sufficient conditions of good-triangles, good-2-sets, and clean pairwise disjoint segments.

Significance. If the proof gaps are filled, the paper determines mu(D(P)) up to an additive constant for large n and gives a universal lower bound with a small additive gap over all n. The constructions are explicit and parameter-free, and the upper bounds are combinatorial counting arguments, which is a strength. The machine-assisted verification for the 7-point example is a useful addition, though it relies on external code. The main weakness is that the n=7, |bP|=6 case of the lower bound rests on an unproved geometric assertion; since this same case supplies the lower-bound half of the sharpness example, the advertised best-possible nature of Theorem 2 is not yet fully demonstrated.

major comments (3)
  1. [Section 3.3, Lemma 19, Case 2] In the proof of Lemma 19, Case 2 (n=7, |bP|=6), the assertions 'It is not hard to see that there must exist i' and 'it is straightforward to check that triangle x v_i v_{i+1} ... is a good-triangle' are not accompanied by a proof. Definition 14(ii) is a global condition on every segment of P\triangle that meets all three sides of the triangle, and the text does not show that the four-element list exhausts all such segments. Cleanliness of xv_i and xv_{i+1} is not claimed, so the 'Evidently' remark after Definition 14 does not apply. This case is the entire proof of Theorem 2 for n=7 with six hull points, and it supplies the lower bound in Proposition 3. Please replace this by a complete geometric proof or by an exhaustive verification over the finitely many order types of seven points with six hull points, with code or a certificate included.
  2. [Section 2, Theorem 1, cases (ii)-(iii)] The proof of Theorem 1 asserts, without proof, that 'P always contains at least two disjoint segments f and h' with the stated disjointness properties, and in the n=5 case that a further segment e exists. These 'it is not hard to see' statements are load-bearing: they establish diam(D(P)) <= 3 for n=6,7,8 and diam(D(P)) <= 4 for n=5, which are used in Lemma 7 and in the upper-bound argument of Theorem 4. Please give explicit constructions or a lemma with proof.
  3. [Section 4, Proposition 3] The upper bound mu(D(P)) <= 12 is delegated to an external Mathematica program referenced only by a shortlink ([17]). The paper gives pseudocode, but no certificate, no independent verifier, and no exact output listing; as published, the reader cannot check the computation without trusting the link. Since Proposition 3 is advertised as showing that Theorem 2 is best possible, and since its lower-bound half depends on the unproved Case 2 of Lemma 19, the computational part should be made self-contained or accompanied by a reproducible certificate.
minor comments (4)
  1. [Section 4, Proposition 3 paragraph] The phrase 'D(P) has no mutually visibility sets of size 13' should read 'no mutual-visibility sets'.
  2. [Section 3.3, Lemma 19, Case 2] The phrase 'x lies on ell+(...)' should be 'x lies in the open half-plane ell+(...)', since half-planes are regions rather than lines.
  3. [Section 1.3, notation] The symbol P is used both for the point set and for the set of segments; this is a common convention but can be confusing in dense case analyses such as Lemma 19, Case 8, where expressions like P = bP union P^c mix the two meanings.
  4. [References] Reference [17] is a tinyurl; the authors should provide a stable URL or include the code as ancillary material so that the computer-assisted proof remains accessible.

Circularity Check

0 steps flagged · score 1.0 of 10

Self-contained derivation: μ(D(P)) bounds are proved from Lemma 7 with explicit excluded-segment sets; self-citations are background only; no fit or definitional identity carries a main claim. Flagged: Lemma 19 Case 2's 'straightforward to check' good-triangle is an omitted proof — a rigor gap for Theorem 2's n=7,|bP|=6 case and Proposition 3's lower half, not circularity.

full rationale

All central claims are proved in-paper from Lemma 7, which is a direct argument: an explicitly chosen set S of s segments satisfying the listed distance conditions gives μ(D(P)) ≥ C(n,2) − s by exhibiting shortest paths whose internal vertices avoid P\S. Lemmas 11, 12, 18, 19, 20, 21 and 22 each construct S explicitly (e.g., Lemma 12's S = {v1v2, v1v3, v1v', v1v4, v2v3, v2v', v2v4, v3v', v4v'}) and verify the conditions by planar case analysis, so the lower bounds are constructive rather than fitted. The upper bounds in Theorem 4 and Proposition 5 are diameter-2 counting arguments built on the in-paper Theorem 1. Proposition 3's upper bound is a brute-force check of all C(21,13) = 203490 13-subsets with code posted at [17] — an exhaustive, externally executable computation, not a fit or a self-citation. Self-citations ([7], [10], [11], [15], [16]) appear only as introduction context (chromatic number, connectivity, Hamiltonicity) or for the elementary fact 'D(P) is connected if and only if n ≥ 5'; none carries the mutual-visibility bounds or the tightness constructions, and no uniqueness theorem or ansatz is imported from the authors' prior work. The one flagged weakness is Lemma 19 Case 2 (n = 7, |bP| = 6): 'If x lies on ℓ+(v_{i+2}v_{i+5}) (resp. ℓ−(v_{i+2}v_{i+5})), then it is straightforward to check that △ = x v_i v_{i+1} (resp. △ = x v_{i+3}v_{i+4}) is a good-triangle.' No verification of Definition 14(ii) is exhibited, and (ii) is a strong global condition on every segment of P\△ meeting all three sides; cleanliness of xv_i and xv_{i+1} does not obviously imply it for segments incident to v_i or v_{i+1}. Since Proposition 15 converts this good-triangle into the C(n,2) − 9 lower bound and Proposition 3 cites this case for its lower half, the omitted proof is a correctness risk for those results; Theorem 4's asymptotics are unaffected because its lower bound uses an Erdős–Szekeres convex 10-subset. An omitted geometric verification is not circularity, however: no conclusion equals its own hypothesis or a fitted parameter. Score 1.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central results introduce no fitted constants and no new theoretical entities. The only inputs are the general-position assumption, standard Erdős-Szekeres background, the prior connectivity fact, and the external computer check for the 7-point example.

assumptions (4)
  • domain assumption P is in general position, meaning no three points are collinear.
    Used throughout to ensure segments intersect in at most one point and to define crossings, clean segments, and hull triangles.
  • standard math The Erdős-Szekeres theorem provides f_ES^2(10): any point set of that size contains 10 points in convex position.
    Invoked in the lower-bound half of Theorem 4 (Section 5) to extract five pairwise disjoint clean boundary segments from a convex 10-subset.
  • domain assumption D(P) is connected if and only if n >= 5, from prior work [10].
    Used at the start of Section 1.4 to reduce to n >= 5 so distances and diameter are finite.
  • ad hoc to paper The external Mathematica program at [17] correctly and exhaustively checks all 21-choose-13 subsets for Proposition 3.
    The upper bound mu(D(P)) <= 12 for the 7-point example rests on this unverified computation; no formal certificate or commit hash is given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Mutual-visibility of the disjointness graph of segments in ${\mathbb R}^2$." pith.science (2026). https://pith.science/paper/FNQNK7K7

@misc{pith2026250600689,
  author       = {Pith},
  title        = {Pith review of: Mutual-visibility of the disjointness graph of segments in $\mathbb R^2$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FNQNK7K7}},
  note         = {Machine review of arXiv:2506.00689}
}
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 almost all edge disjointness graphs have diameter 2.

Figures

Figures reproduced from arXiv: 2506.00689 by the authors.

Figure 1
Figure 1. The 7-point set in general position {p1, p2, . . . , p7} in (a) is P. In particular, we note that Pb = P \ {p7}. In (b) we have P, which can be seen as the rectilinear drawing of K7 induced by P. Observe that CH(P) is the convex hexagon formed by the union of segments p1p2, p2p3, p3p4, p4p5, p5p6, and p6p1. The graph in (c) is D(P) and has diameter 3. The red vertex set is a visible set of D(P) of size 12. The red v… view at source ↗
Figure 2
Figure 2. If Pb = {v1, v2, v3}, then v − i v + i vi+1vi+2 form a convex quadrilateral for some i ∈ {1, 2, 3}, addition taken mod 3. Lemma 11. If n ≥ 5 and |Pb| = 3, then µ(D(P)) ≥ n 2  − 8. Proof. Let u, v, w be the points in Pb, and suppose that they appear in this cyclic order on Pb. Let u − (respectively, u +) be the first (respectively, last) point in P \ Pb that we find as we rotate ℓ(uv) clockwise around u. By Proposit… view at source ↗
Figure 3
Figure 3. The set formed by the 8 (respectively, 9) continuous seg￾ments of the drawing on the left (respectively, right) is S [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Then b must intersect er, as otherwise er is the required f. From b ∩ er ̸= ∅, and the fact that b has exactly one endpoint in {u, v, x, y} it is easy to see that b does not intersect the interior of L, and so we have a ∩ b = ∅, a contradiction. □ [PITH_FULL_IMAGE:fig…
Figure 5
Figure 5. Figure 5: On the left we have |Pb| = 5 showing the labels that we use for the points and the regions of D5 that are incident with Pb. This notation is used in all the proofs given in Section 3.3. On the right we have |Pb| = 7, and the labeling depicted is used only in the proof …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

  1. [17]

    L. R. R ´ ıos-Castro,https://tinyurl.com/bdfa534b

    work page

  2. [1]

    Aichholzer, J

    O. Aichholzer, J. Kynˇ cl, M. Scheucher, and B. Vogtenhuber. On 4–Crossing-Families in Point Sets and an Asymptotic Upper Bound. InProceedings of the 37th European Workshop on Computational Geometry (EuroCG 2021)pp. 1–8 (2021)

    work page 2021

  3. [2]

    Araujo, A

    G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy, and J. Urrutia. On the chromatic number of some geometric type Kneser graphs.Comput. Geom., 32(1):59–69, 2005

    work page 2005

  4. [3]

    Bujt´ as, S

    C. Bujt´ as, S. Klavˇ zar, J. Tian, Total mutual-visibility in Hamming graphs, Opuscula Math. 45, no. 1 (2025), 63-78, https://doi.org/10.7494/OpMath.2025.45.1.63

    doi:10.7494/opmath.2025.45.1.63 2025

  5. [4]

    Cicerone, G

    S. Cicerone, G. Di Stefano and S. Klavˇ zar, On the mutual visibility in Cartesian products and triangle-free graphs,Appl. Math. Comput.438(2023), Paper No. 127619, 9 pp

    work page 2023

  6. [5]

    Cicerone, G

    S. Cicerone, G. Di Stefano, S.Klavˇ zar and I. G. Yero, Mutual-visibility problems on graphs of diameter two,European J. Comb.120(2024), Paper No. 103995

    work page 2024

  7. [6]

    Erd˝ os, G

    P. Erd˝ os, G. Szekeres, A combinatorial problem in geometry. Compositio Mathematica, Vol- ume 2 (1935), pp. 463-470

    work page 1935

  8. [7]

    J. J. Garc ´ ıa-Davila, J. Lea˜ nos, M. Lome ´ ı, and L. R. R ´ ıos-Castro, The maximum chromatic number of the disjointness graph of segments onn-point sets in the plane withn≤16.Bol. Soc. Mat. Mex., (2024) 30, 85

    work page 2024

Show all 23 references
  1. [8]

    Dettlaff, M

    M. Dettlaff, M. Lema´ nska, J. A. Rodr ´ ıguez-Vel´ azquez and I. G. Yero, Mobile mutual-visibility sets in graphs.Ars Mathematica Contemporanea,24 (1)(2025)

    2025

  2. [9]

    G. B. Ekinci and C. Bujt´ as, Mutual-visibility problems in Kneser and Johnson graphs.Ars Mathematica Contemporanea,44 (1)(2025)

    2025

  3. [10]

    An Upper Bound Asymp- totically Tight for the Connectivity of the Disjointness Graph of Segments in the Plane

    Espinoza-Valdez, A.; Lea˜ nos, J.; Ndjatchi, C.; R ´ ıos-Castro, L.M. An Upper Bound Asymp- totically Tight for the Connectivity of the Disjointness Graph of Segments in the Plane. Symmetry2021,13, 1050. https://doi.org/10.3390/sym13061050

    doi

  4. [11]

    Fabila-Monroy, C

    R. Fabila-Monroy, C. Hidalgo-Toscano, J. Lea˜ nos, and M. Lomel ´ ı-Haro, The Chromatic Num- ber of the Disjointness Graph of the Double Chain. InDiscrete Mathematics and Theoretical Computer Science,22:1, 2020, #11

    2020

  5. [12]

    Fabila-Monroy and D

    R. Fabila-Monroy and D. R. Wood. The chromatic number of the convex segment disjointness graph. InComputational geometry, volume 7579 ofLecture Notes in Comput. Sci., pages 79–

  6. [13]

    J. Jonsson. The exact chromatic number of the convex segment disjointness graph, 2011

    2011

  7. [14]

    Kneser.Jahresbericht der Deutschen Mathematiker-Vereinigung, volume 58, page 27

    M. Kneser.Jahresbericht der Deutschen Mathematiker-Vereinigung, volume 58, page 27

  8. [15]

    Lea˜ nos, C

    J. Lea˜ nos, C. Ndjatchi, and L. R. R ´ ıos-Castro, On the connectivity of the disjointness graph of segments of point sets in general position in the plane.Discrete Mathematics and Theoretical Computer Science (DMTCS), vol. 24 : 1,2022,#15,1−16

    2022

  9. [16]

    Lea˜ nos, C

    J. Lea˜ nos, C. Ndjatchi, and L. R. R ´ ıos-Castro, Disjointness graphs of segments inR 2 are almost all hamiltonian.Discrete Applied Mathematics, 342 (2024) 168-173

    2024

  10. [18]

    Lov´ asz, Kneser’s conjecture, chromatic number, and homotopy,J

    L. Lov´ asz, Kneser’s conjecture, chromatic number, and homotopy,J. Combin. Theory Ser. A,25 (1978), 319–324

    1978

  11. [19]

    J. Pach, G. Tardos, and G. T´ oth, Disjointness graphs of segments, in:Boris Aronov and Matthew J. Katz (eds.), 33th International Symposium on Computational Geometry (SoCG 2017) , vol. 77 of Leibniz International Proceedings in Informatics (LIPIcs), 59:1– 15, Leibniz-Zentrum ...

    2017

  12. [20]

    G. D. Stefano, Mutual visibility in graphs,Appl. Math. Comput.419(2022). Article 126850

    2022

  13. [21]

    Wolfram Research, Inc., Mathematica, Version 12.0, Champaign, IL, (2019)

    2019

  14. [84]

    Springer, Cham, 2011

    2011

  15. [1956]

    MUTUAL-VISIBILITY OF THE DISJOINTNESS GRAPH OF SEGMENTS INR2 19

    Aufgabe 360. MUTUAL-VISIBILITY OF THE DISJOINTNESS GRAPH OF SEGMENTS INR2 19

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.