{"id":"98105cbf-63d9-42fa-a3e1-7b8961db2a51","arxiv_id":"1908.08871","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"All four variants of the segment number are ∃R-complete to decide, and there exist planar graphs where the classical segment number is asymptotically twice the 3D, bend, or crossing variant.","lead":"This paper studies three new versions of the segment number, the fewest straight pieces needed to draw a graph: drawings with bends, drawings in 3D, and drawings where edges may cross. It shows all are hard to compute exactly and gives bounds for cubic graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's placement invariant is not established: in Case II' the stated avoidance rule does not exclude the point where the new line vi'vj meets a line m that is skew to both ell and ell'.","rationale":"The reader's conditional verdict points to Theorem 5 as the weakest assumption. I agree that the placement invariant is the load-bearing part, but I would sharpen the concern: the charging argument is likely salvageable, while the Case II' avoidance rule as written is genuinely insufficient when a third line m is skew to both ell and ell'. The theorem may still be true with a corrected avoidance rule, so this is a proof gap rather than a known counterexample. Since the paper's other main contributions (the separation construction, the existential-real completeness, and the connectivity bounds for cubic graphs) are either supported by known results or have more standard proofs, the overall verdict should remain conditional pending a rigorous treatment of the placement invariant. A concrete algebraic check can demonstrate the incompleteness of the stated rule and guide the necessary patch.","tokens_in":11802,"tokens_out":33884,"duration_ms":344086,"concrete_test":"Take a partial configuration matching Case II' second subcase: lines ell and ell' in L with vi and vi' as their last vertices, and a third line m skew to both ell and ell'. Compute the point p = ell cap span(m, vi') and test whether p lies in the union of planes spanned by pairs of non-skew lines in L. If p is found outside that union, the proof's stated avoidance rule admits vj = p, and then vi'vj intersects m, violating the invariant. This symbolic linear-algebra check on a few random line sets will settle whether the stated rule is incomplete; if the gap is confirmed, patch the rule to forbid all planes span(m, vi') and verify that such a placement always exists.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is in Theorem 5, Case II' (second subcase), where both predecessors vi and vi' are the last vertices on their lines ell and ell', and each already has an earlier successor not on its line. The proof places vj on ell and adds the line vi'vj. To maintain the invariant, vi'vj must be skew to every other line m in L, except lines that already intersect ell' at vi' or ell at vj. The proof says only to avoid placing vj on a plane spanned by two non-skew lines in L. But if m is skew to both ell and ell', the dangerous positions for vj are the intersection of ell with the plane span(m, vi'), and this plane is not generally spanned by two lines of L. Hence the stated avoidance rule does not rule out a crossing, and the invariant is not actually proved. The later charging claim (each non-end vertex has a flat predecessor or v1) appears derivable from the cases once such placements exist, so the placement invariant is the real weak point. If some biconnected cubic graph admits no such placement, the bound seg3(G) <= n+2 collapses.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":98,"tokens_out":37981,"duration_ms":452923,"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":[{"comment":"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.","section":"§4.2, Theorem 5, Case II' (second subcase)"},{"comment":"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.","section":"§3, Theorem 2"},{"comment":"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.","section":"§2, Proposition 1"}],"minor_comments":[{"comment":"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.","section":"§3, Theorem 3"},{"comment":"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.","section":"§4.2, Theorem 5"},{"comment":"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.","section":"§2, Proposition 1"},{"comment":"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.","section":"§4.1, Theorem 4"},{"comment":"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.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The main claims are likely correct, but the manuscript currently contains two load-bearing proof gaps (the placement invariant in Theorem 5 and the false inequality in Theorem 2) and an under-proved lower bound in Proposition 1. These are repairable, but they require substantive additions rather than copy-editing. I recommend major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper is a solid contribution to the visual-complexity literature. It actually delivers what it promises: an infinite family of planar graphs where the classical 2D segment number is asymptotically twice the 3D, crossing, and bend variants; ∃R-completeness for all four variants (which also gives NP-hardness); and new bounds for cubic graphs that depend on connectivity. The separation construction is clever, and the reductions in Section 3 are carefully adapted from Chaplick et al.'s line-cover hardness. The cubic-graph counting arguments (Lemma 2 and the charging scheme) are clean and give genuine improvements.\n\nThe soft spots are real but not load-bearing-fatal in my reading. Proposition 1's fan lower bound ('each i-fan needs at least i−3 disjoint segments') is asserted in a sentence; it is plausible but deserves a formal proof. Theorem 4's segment count assumes that in the Liu et al. orthogonal drawing exactly one segment ends at each vertex; that property is not established here, and it is not true for an arbitrary orthogonal drawing of a cubic graph. The proof needs to cite or prove that the specific algorithm has this property.\n\nTheorem 5 has a more substantive gap, and the stress-test note is right about it. In Case II' the text says to avoid placing vj on a plane spanned by two non-skew lines in L. But the dangerous positions for the new line v_i'v_j relative to a line m that is skew to both ℓ and ℓ' are the intersection of ℓ with the plane span(v_i', m); that plane is not generally spanned by two lines of L. So the stated avoidance rule is insufficient. The fix is straightforward—there are finitely many forbidden x-positions along ℓ, so one can choose ε to miss them—but as written the invariant proof is incomplete. The later charging claim then depends on that placement, so the bound seg3(G) ≤ n+2 is not yet fully established.\n\nNone of this makes me think the main results are wrong. The complexity results rest on published ∃R-complete benchmarks, the separation family is easy to verify, and the cubic bounds have the right feel. The proofs need tightening before publication, not a different research direction.\n\nThis is the kind of paper a good referee should engage with: the questions are natural, the results are useful, and the gaps are specific and fixable. I would send it to a serious referee rather than desk-reject it.\n\nBest.","headline":"Solid new results on segment-number variants, with a few proof gaps that are patchable rather than fatal.","tokens_in":12528,"tokens_out":7494,"would_cite":true,"duration_ms":69658,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","68R10","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Relaxing planarity, straightness, or dimension can halve the segment number of planar graphs, and all four variants are ∃R-complete to compute.","keywords":["segment number","graph drawing","∃R-complete","cubic graphs","3D graph drawing","polyline drawings","arrangement graphs","visual complexity"],"falsifier":"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.","tokens_in":11593,"feed_emoji":"📐","tokens_out":11245,"duration_ms":104164,"temperature":0.7,"pith_summary":"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.","feed_headline":"For some graphs, 3D halves segment count","feed_subtitle":"Bends and crossings give the same halving; computing any variant is ∃R-complete.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the segment number and planar slope number, and supplies the upper bound seg2(Ti) ≤ 5ti/2 used in the ratio construction, as well as the earlier triconnected cubic bound that the paper builds on.","marker":"[5]"},{"why":"Establishes ∃R-hardness for the line cover numbers and supplies the tail-gadget and reduction pattern that the paper reuses to prove hardness of all segment-number variants.","marker":"[3]"},{"why":"Proves Arrangement Graph Recognition is NP-hard, providing the hard graphs that the reductions in Theorem 1 are built from.","marker":"[1]"},{"why":"Shows Arrangement Graph Recognition is ∃R-complete, giving the hardness and membership context for the segment-number decision problems.","marker":"[8]"},{"why":"Proves that stretchability of pseudolines is NP-hard, the underlying result that powers the arrangement-graph hardness proof.","marker":"[20]"},{"why":"Provides the at-most-one-bend orthogonal drawing algorithm for biconnected planar cubic graphs, which the paper counts to obtain seg∠ ≤ n+1.","marker":"[14]"},{"why":"Gives the linear-time st-numbering algorithm used as the ordering mechanism for the 3D construction in Theorem 5.","marker":"[9]"},{"why":"Provides the exact seg2 = n/2+3 bound for triconnected cubic planar graphs that appears in Table 1 and sets the comparison baseline for the new cubic bounds.","marker":"[16]"}],"fun_headline_variants":["3D, bends, or crossings can halve segment needs","Segment number variants halve costs, are ∃R-complete","Planar segment number not intrinsic: variants halve it","Cubic graphs: new segment bounds and algorithms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["3D, bends, or crossings can halve segment needs","Segment number variants halve costs, are ∃R-complete","Planar segment number not intrinsic: variants halve it","Cubic graphs: new segment bounds and algorithms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000207,"raw_usage":{"total_tokens":1381,"prompt_tokens":908,"completion_tokens":473,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":524,"completion_tokens_details":{"reasoning_tokens":406}},"tokens_in":524,"tokens_out":473,"duration_ms":4922,"temperature":1.0,"reasoning_tokens":406,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:30:33.128736+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves Arrangement Graph Recognition is NP-hard, providing the hard graphs that the reductions in Theorem 1 are built from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows Arrangement Graph Recognition is ∃R-complete, giving the hardness and membership context for the segment-number decision problems."},{"cited_title":"In: Gritzmann, P., Sturm- fels, B","cited_arxiv_id":null,"evidence_quote":"Proves that stretchability of pseudolines is NP-hard, the underlying result that powers the arrangement-graph hardness proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the at-most-one-bend orthogonal drawing algorithm for biconnected planar cubic graphs, which the paper counts to obtain seg∠ ≤ n+1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the exact seg2 = n/2+3 bound for triconnected cubic planar graphs that appears in Table 1 and sets the comparison baseline for the new cubic bounds."}],"review_version":1}