Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Variants of the Segment Number of a Graph

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Relaxing planarity, straightness, or dimension can halve the segment number of planar graphs, and all four variants are ∃R-complete to compute.

desk verdict Solid new results on segment-number variants, with a few proof gaps that are patchable rather than fatal. read the letter →

arxiv 1908.08871 v2 pith:5PEDZQ4H submitted 2019-08-23 cs.CG cs.DM

Yoshio Okamoto , Alexander Ravsky , Alexander Wolff This is my paper · ORCID
classification cs.CGcs.DM MSC 05C1005C6268R1068U05
keywords segmentnumbergraphdrawing∃R-completecubicgraphs3Dpolylinedrawingsarrangementvisualcomplexity
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 three relaxations of the segment number, the minimum number of straight-line segments needed to draw a planar graph crossing-free in the plane: allowing bends in a 2D polyline drawing, allowing crossings in a 2D straight-line drawing, and moving to crossing-free straight-line drawings in 3D. Its central result is that for a carefully built infinite family of planar graphs, the classical planar segment number is asymptotically twice as large as each of the three new variants. It then proves that deciding whether any of the four numbers is at most a given k is ∃R-complete, hence NP-hard, even for graphs of maximum degree 4. For cubic graphs, it supplies new lower and upper bounds, including seg3(G) ≤ n+2 and seg×(G) ≤ n+2 for every biconnected cubic graph, and seg∠(G) ≤ n+1 for every biconnected planar cubic graph. These bounds matter because the segment number is a standard measure of visual complexity, and the results delimit how much visual complexity can be saved by extra dimensions, bends, or allowed crossings.

What carries the argument

The key identity is Lemma 2: in any straight-line drawing of a cubic graph, the number of segments equals n/2 + t + b, where t is the number of 'tripod' vertices at which three segments end and b is the number of bends. Nearly all cubic-graph results reduce to counting these objects on convex hulls or in placement invariants. The other load-bearing mechanism is the st-numbering construction of Theorem 5, which threads the vertices of a biconnected cubic graph one by one into 3D, maintaining a set L of lines that are pairwise skew or meet only at already placed vertices; the proof charges each new vertex to a 'flat' predecessor to keep the tripod count low, yielding the n+2 upper bound. For the hardness results, the load-bearing reduction is arrangement graph recognition, reusing a tail-gadget from the line-cover reduction and the equivalence between line-cover number, segment number, and the new variants on the constructed graph.

What would settle it

Exhibit a biconnected cubic graph and an st-numbering where Case II' (a vertex whose two predecessors are both non-flat last vertices on their lines) forces a placement that makes a new line coplanar with an earlier line away from any already placed vertex; such a graph would violate the invariant in Theorem 5 and show the n+2 bound is not established by the construction.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the classical planar segment number is not an intrinsic measure of drawing efficiency: there are planar graphs for which seg2 is asymptotically twice seg3, seg∠, and seg×, so giving up planarity, straightness, or two-dimensionality individually saves a linear fraction of the geometric primitives. The paper further shows that computing any of the four variants is ∃R-complete, in the same sense that deciding the line cover number is ∃R-complete; the reduction works from arrangement graph recognition, and the instance graphs have maximum degree 4. For cubic graphs, the paper establishes both existential lower bounds and algorithmic upper bounds: connected cubic graphs can require 5n/6 segments in every style, biconnected planar cubic graphs have seg∠ ≤ n+1 via a single-bend orthogonal drawing, and every biconnected cubic graph has seg3 ≤ n+2 and seg× ≤ n+2 via an st-numbering construction in 3D.

Load-bearing premise

The proof that every biconnected cubic graph can be drawn in 3D with at most n+2 segments depends on the assumption that the step-by-step st-numbering placement always gives every intermediate vertex a predecessor that is 'flat' (only one drawn segment ends there) or is the starting vertex; if any placement case forces otherwise, the counting argument and the bound fail.

Editorial extensions

If this is right

  • Because every graph has seg× ≤ seg3, any drawing with crossings in 2D is at least as efficient as a 3D straight-line drawing; the fan construction shows the gap to the planar segment number can be a factor of two asymptotically.
  • The four decision problems seg2 ≤ k, seg3 ≤ k, seg∠ ≤ k, and seg× ≤ k are ∃R-complete, and hence NP-hard, already for graphs of maximum degree 4, so no polynomial-time algorithm is expected for any of them.
  • Every biconnected cubic graph with n vertices has seg3(G) ≤ n+2 and seg×(G) ≤ n+2, and every biconnected planar cubic graph has seg∠(G) ≤ n+1, with a linear-time drawing algorithm in the bend case.
  • There are connected cubic graphs on 6k−2 vertices requiring 5k−1 segments in every style, and triconnected cubic graphs requiring 7n/10 segments in 3D, so the new variants are not constant-factor close to the n/2+3 optimum across all connectivities.

Reading between the lines

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

  • Inference: if the st-numbering 3D construction can be made fully formal in every case, the same flat-vertex charging may yield n+O(1) segment bounds for wider classes of bounded-degree graphs, including 4-regular planar graphs, where the paper's Open Problem 2 asks for such bounds.
  • Inference: since seg× ≤ seg3 via projection, any improved lower bound for seg× immediately transfers to the 3D segment number; conversely, the 7n/10 lower bound for triconnected cubic graphs suggests that 3D drawings of high-connectivity cubic graphs still need linear overhead.
  • Inference: a natural guess implied by the ratio-2 construction is that 2 is the worst possible asymptotic ratio between seg2 and each variant for planar graphs; testing this would require constructing families with ratios approaching every value in [1, 2].
  • Inference: the ∃R-completeness at maximum degree 4 leaves open degree 3; a plausible next step is to adapt the tail-and-arrangement reduction to subcubic graphs, which would nearly settle the earlier open question about the 3D segment number for subcubic graphs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper introduces and studies three variants of the segment number: the 3D segment number seg3, the crossing segment number seg×, and the bend segment number seg∠. It establishes relationships among these parameters (Lemma 1, Corollary 1), constructs an infinite family of planar graphs in which the classical segment number is asymptotically twice as large as each new variant (Proposition 1), proves ∃R-completeness for deciding all four parameter values, even for maximum degree 4 in the planar and 3D cases (Theorems 1–3), and gives upper and lower bounds for cubic graphs depending on connectivity (Section 4, Table 1). In particular, it claims seg∠(G)≤n+1 for biconnected planar cubic graphs (Theorem 4), seg3(G)≤n+2 and seg×(G)≤n+2 for all biconnected cubic graphs (Theorem 5), and additional bounds for connected, biconnected, and triconnected classes (Propositions 2–5).

Significance. If the proofs are completed, the paper makes a solid contribution to graph drawing: it introduces natural visual-complexity parameters, gives the first hardness results for them, and provides nontrivial bounds for cubic graphs. The reductions are built on established ∃R-complete problems such as arrangement-graph recognition, and the paper explicitly credits prior work by Chaplick et al. and Dujmović et al. The manuscript contains no fitted parameters and no circular derivations. The separation examples (Proposition 1) and the cubic-graph charging argument are conceptually appealing. However, several load-bearing proof steps are currently incomplete, so the claims, while plausible, are not yet fully established.

major comments (3)
  1. [§4.2, Theorem 5, Case II' (second subcase)] The placement invariant is not proved. In the case where both predecessors vi and vi' are last on their lines 𝓁 and 𝓁' and have earlier successors not on those lines, the proof places vj on 𝓁 and adds the line vi'vj. The stated avoidance rule—avoid planes spanned by two non-skew lines of L—does not exclude the point p_m = 𝓁 ∩ span(vi', m) for a line m that is skew to both 𝓁 and 𝓁'. At that point, vi'vj is coplanar with m, violating the invariant. Since the invariant is the only argument preventing edge crossings, the construction as written does not guarantee that a valid placement exists for every biconnected cubic graph. The subsequent charging claim that every non-first/non-last vertex has a flat predecessor or v1 is also asserted without being derived from the case analysis. This gap is load-bearing for the bound seg3(G)≤n+2 and must be repaired.
  2. [§3, Theorem 2] The step 'By definition, we immediately obtain seg3(G′)≤ρ1_3(G′)' is incorrect in general: a line-cover drawing can use fewer lines than the number of segments because one line may contain several disjoint edge-segments. Thus ρ1_3 is a lower bound, not an upper bound, for seg3. The theorem is salvageable—for yes-instances the explicit arrangement drawing gives seg3(G′)≤k, and if seg3(G′)≤k then seg×(G′)≤seg3(G′)≤k, so Theorem 1 applies—but the proof as written does not establish the claimed equality or the hardness reduction.
  3. [§2, Proposition 1] The lower-bound argument for the 2D segment number of the graphs Si is not demonstrated. The claim that an i-fan attached to an inner vertex 'needs at least i−3 segments that are disjoint from the drawing of the triangulation' requires a careful count of how many of the i+1 spokes and i path edges can be merged with the at most six incident triangulation segments. Without such an argument, the asymptotic lower bound seg2(Si)≥i^3−O(i^2) is not established, and the factor-2 separation, which is a central contribution, rests on an unproved assertion.
minor comments (5)
  1. [§3, Theorem 3] The first-order formula uses the variable k both as the number of segments and as a vertex index, and it does not exclude i=j. As written, the implication forces {i,i}∈E for every vertex lying on a line, making the formula unsatisfiable for any drawing. Rename the vertex index and add the condition i≠j.
  2. [§4.2, Theorem 5] The initial statement that vertex vj has x-coordinate j±ε is inconsistent with the case analysis, which mostly places vj in the plane x=j and only in one subcase uses x=j+ε. The base case for v2 and v1 is also not explicitly addressed when no line containing v1 yet exists.
  3. [§2, Proposition 1] The definition of an i-fan and the counting in the 3D upper bound need clarification: a path of length i has i+1 vertices, yet the bound ti·(i/2+3) suggests a pairing of i+1 spokes into i/2 segments. Please state the exact number of new vertices and the precise segment count for the 3D drawing of a fan.
  4. [§4.1, Theorem 4] The statement 'In any vertex exactly one segment ends' should be qualified as a property of the orthogonal drawing produced by the algorithm of Liu et al., not of arbitrary polyline drawings of cubic graphs.
  5. [Table 1] The table layout for the γ=2 row is difficult to parse; the entries for seg3, seg∠, and seg× should be aligned with their column headers and with the theorems that prove them.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's bounds and hardness proofs are constructive reductions from independent external results, with possible proof gaps but no self-referential derivation.

full rationale

The derivation chain is not circular. Proposition 1 is an explicit construction with independent lower-bound and upper-bound arguments; no quantity is fitted to the target values. The hardness results reduce from Arrangement Graph Recognition via the five-way equivalence in Theorem 1, which re-proves the segment-specific implications rather than assuming them. The cited work of Chaplick et al. [3] is a published prior result on line-cover numbers; even though two of the present authors co-authored it, the current proof adds the implications involving seg2, seg3, seg∠, and seg×, so the target claims are not assumed. The cubic-graph bounds are constructive: Theorem 5 uses an st-numbering and a placement invariant, and the charging argument is a potential proof gap if the invariant is not fully established, but that is a correctness concern, not circularity. Similarly, the inequality direction seg3(G') ≤ ρ1_3(G') in Theorem 2 appears suspect, but a wrong inequality is not a circular definition or a fitted input relabeled as a prediction. No conclusion in the paper is equivalent to its own input by construction.

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

The central claims rest on external computational-geometry results and known drawing algorithms rather than on fitted data. The most fragile unstated input is the segment-end property of Liu et al.'s orthogonal drawings used in Theorem 4.

assumptions (5)
  • domain assumption Arrangement Graph Recognition is ∃R-complete
    Used in Theorems 1 and 2 as the source of hardness for the reductions to segment-number variants.
  • domain assumption Chaplick et al. proved ∃R-hardness and ∃R-membership for the line cover numbers ρ1_2 and ρ1_3
    Theorem 3 reuses their first-order expression over the reals and extends it to segment-number variants; the cited result is by overlapping authors but is published.
  • domain assumption Liu et al. draw every biconnected planar cubic graph except K4 orthogonally with at most one bend per edge, at most n/2+1 bends, and exactly one segment ending at each vertex
    Theorem 4's bound seg∠≤n+1 is computed from these properties; the last property is asserted in the paper but not verified from the cited source.
  • standard math Existence of st-numberings for biconnected graphs
    Theorem 5 orders vertices by an st-numbering; this is a standard linear-time result from Even and Tarjan.
  • standard math Steinitz theorem: every triconnected planar graph is the 1-skeleton of a 3D convex polyhedron
    Proposition 5 starts from an arbitrary triconnected cubic graph drawn as a polyhedron.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Variants of the Segment Number of a Graph." pith.science (2026). https://pith.science/paper/5PEDZQ4H

@misc{pith2026190808871,
  author       = {Pith},
  title        = {Pith review of: Variants of the Segment Number of a Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5PEDZQ4H}},
  note         = {Machine review of arXiv:1908.08871}
}
abstract

The \emph{segment number} of a planar graph is the smallest number of line segments whose union represents a crossing-free straight-line drawing of the given graph in the plane. The segment number is a measure for the visual complexity of a drawing; it has been studied extensively. In this paper, we study three variants of the segment number: for planar graphs, we consider crossing-free polyline drawings in 2D; for arbitrary graphs, we consider crossing-free straight-line drawings in 3D and straight-line drawings with crossings in 2D. We first construct an infinite family of planar graphs where the classical segment number is asymptotically twice as large as each of the new variants of the segment number. Then we establish the $\exists\mathbb{R}$-completeness (which implies the NP-hardness) of all variants. Finally, for cubic graphs, we prove lower and upper bounds on the new variants of the segment number, depending on the connectivity of the given graph.

Figures

Figures reproduced from arXiv: 1908.08871 by the authors.

Figure 1
Figure 1. Attaching a fan (thin edges) to a vertex of a triangulation (thick edges) of maximum degree 6 Fig. 1a. Each such i-fan must be placed into a triangular face and needs at least i − 3 segments that are disjoint from the drawing of the triangulation. (Here we use that every vertex has degree at most 6.) Hence, seg2 (Si) ≥ (ti −3)·(i−3) = i 3 − O(i 2 ). In 3D on the other hand, we can draw every fan in a plane different… view at source ↗
Figure 2
Figure 2. The graph Gk (here k = 4) is a caterpillar with k − 2 inner vertices of degree 3 where each leaf has been replaced by a copy of the 5-vertex graph K0 4 (shaded gray). Lemma 2. For any straight-line drawing δ of a cubic graph with n vertices, seg(δ) = 3n/2 − f(δ) + b(δ) = n/2 + t(δ) + b(δ). Proof. Clearly, n = f(δ) + t(δ). The number of “segment ends” is 3t(δ) + f(δ) + 2b(δ) = 3n − 2f(δ) + 2b(δ) = n + 2t(δ) + 2b(δ). … view at source ↗
Figure 3
Figure 3. The cubic graph Hk (here k = 4) is a k-cycle whose vertices are replaced by K3,3 minus an edge (shaded) [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 5
Figure 5. Figure 5: Gadget for the proof of Proposition 5 In order to bound seg3 (Fk) from below, we consider two possibilities for the drawing of each subgraph K2,3; either it lies in a plane or it doesn’t. In the planar case, the convex hull of the drawing has at least three extreme poi…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Parameterized Complexity of Computing the Linear Vertex Arboricity

    cs.CC 2025-05 conditional novelty 6.0 of 10

    Deciding whether a graph has linear vertex arboricity 2 is NP-hard for maximum degree 5, NP-hard for planar graphs of maximum degree 6, and fixed-parameter tractable by treewidth.

Reference graph

Works this paper leans on

21 extracted references · 14 canonical work pages · cited by 1 Pith paper

  1. [1]

    Bose, P., Everett, H., Wismath, S.K.: Properties of arrange- ment graphs. Int. J. Comput. Geom. Appl. 13(6), 447–462 (2003). https://doi.org/10.1142/S0218195903001281

    work page doi:10.1142/s0218195903001281 2003

  2. [2]

    Drawing Graphs on Few Lines and Few Planes

    Chaplick, S., Fleszar, K., Lipp, F., Ravsky, A., Verbitsky, O., Wolff, A.: Drawing graphs on few lines and few planes. In: Hu, Y., N¨ ollenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 166–180. Springer (2016). https://doi.org/10.1007/978-3-319- 50106-2 14, http://arxiv.org/abs/1607.01196 Variants of the Segment Number of a Graph 13

    work page Pith review arXiv 2016

  3. [3]

    In: Ellen, F., Kolokolova, A., Sack, J.R

    Chaplick, S., Fleszar, K., Lipp, F., Ravsky, A., Verbitsky, O., Wolff, A.: The com- plexity of drawing graphs on few lines and few planes. In: Ellen, F., Kolokolova, A., Sack, J.R. (eds.) WADS 2017. LNCS, vol. 10389, pp. 265–276. Springer (2017). https://doi.org/10.1007/978-3-319-62127-2 23, arxiv.org/1607.06444

    arXiv 2017

  4. [4]

    Chapman & Hall/CRC, 1st edn

    Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall/CRC, 1st edn. (2008)

    work page 2008

  5. [5]

    Dujmovi´ c, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs with few slopes and segments. Comput. Geom. Theory Appl. 38(3), 194–212 (2007). https://doi.org/10.1016/j.comgeo.2006.09.002

    doi:10.1016/j.comgeo.2006.09.002 2007

  6. [6]

    In: Proc

    Durocher, S., Mondal, D.: Drawing plane triangulations with few segments. In: Proc. Canad. Conf. Comput. Geom. (CCCG’14). pp. 40–45 (2014), http://cccg. ca/proceedings/2014/papers/paper06.pdf

    work page 2014

  7. [7]

    Durocher, S., Mondal, D., Nishat, R., Whitesides, S.: A note on minimum-segment drawings of planar graphs. J. Graph Algorithms Appl. 17(3), 301–328 (2013). https://doi.org/10.7155/jgaa.00295

    work page doi:10.7155/jgaa.00295 2013

  8. [8]

    Eppstein, D.: Drawing arrangement graphs in small grids, or how to play planarity. J. Graph Algorithms Appl. 18(2), 211–231 (2014). https://doi.org/10.7155/jgaa.00319

    work page doi:10.7155/jgaa.00319 2014

Show all 21 references
  1. [9]

    Even, S., Tarjan, R.E.: Computing an st-numbering. Theoret. Comput. Sci. 2(3), 339–344 (1976). https://doi.org/10.1016/0304-3975(76)90086-4

    1976 doi

  2. [10]

    Hoffmann, U.: On the complexity of the planar slope number problem. J. Graph Algorithms Appl. 21(2), 183–193 (2017). https://doi.org/10.7155/jgaa.00411

    2017 doi

  3. [11]

    In: Bodlaender, H.L., Woegin- ger, G.J

    H¨ ultenschmidt, G., Kindermann, P., Meulemans, W., Schulz, A.: Drawing planar graphs with few geometric primitives. In: Bodlaender, H.L., Woegin- ger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 316–329. Springer (2017). https://doi.org/10.1007/978-3-319-68705-6 24

    2017 doi

  4. [12]

    Igamberdiev, A., Meulemans, W., Schulz, A.: Drawing planar cubic 3-connected graphs with few segments: Algorithms & experiments. J. Graph Algorithms Appl. 21(4), 561–588 (2017). https://doi.org/10.7155/jgaa.00430

    2017 doi

  5. [13]

    In: Archambault, D., T´ oth, C.D

    Kindermann, P., Mchedlidze, T., Schneck, T., Symvonis, A.: Drawing planar graphs with few segments on a polynomial grid. In: Archambault, D., T´ oth, C.D. (eds.) GD

  6. [14]

    Liu, Y., Marchioro, P., Petreschi, R.: At most single-bend embeddings of cubic graphs. Appl. Math. 9(2), 127–142 (1994). https://doi.org/10.1007/BF02662066

    1994 doi

  7. [15]

    ArXiv report (2014), http: //arxiv.org/abs/1406.2636

    Matouˇ sek, J.: Intersection graphs of segments and∃R. ArXiv report (2014), http: //arxiv.org/abs/1406.2636

    2014 arXiv

  8. [16]

    Mondal, D., Nishat, R.I., Biswas, S., Rahman, M.S.: Minimum-segment convex drawings of 3-connected cubic plane graphs. J. Comb. Optim. 25(3), 460–480 (2013). https://doi.org/10.1007/s10878-011-9390-6

    2013 doi

  9. [17]

    Mukkamala, P., Szegedy, M.: Geometric representation of cubic graphs with four directions. Comput. Geom. Theory Appl. 42(9), 842–851 (2009). https://doi.org/10.1016/j.comgeo.2009.01.005

    2009 doi

  10. [18]

    In: Epp- stein, D., Gansner, E.R

    Schaefer, M.: Complexity of some geometric and topological problems. In: Epp- stein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334–344. Springer (2010). https://doi.org/10.1007/978-3-642-11805-0 32

    2010 doi

  11. [19]

    Schulz, A.: Drawing graphs with few arcs. J. Graph Algorithms Appl. 19(1), 393– 412 (2015). https://doi.org/10.7155/jgaa.00366

    2015 doi

  12. [20]

    In: Gritzmann, P., Sturm- fels, B

    Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Gritzmann, P., Sturm- fels, B. (eds.) Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift, DIMACS Series in Discrete Math. and Theor. Comput. Sci., vol. 4, pp. 531–554. Amer. Math. Soc. (1991)

    1991

  13. [2019]

    LNCS, Springer (2019), https://arxiv.org/abs/1903.08496, to appear

    2019 arXiv

Pith tools

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