{"id":"936b9688-9979-44bc-83b7-53f8463f4afa","arxiv_id":"1908.04524","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every 4-connected plane triangulation on n vertices has a straight-line drawing whose vertices lie on at most sqrt(2n) horizontal or vertical lines, and the same holds for all subgraphs.","lead":"Stefan Felsner shows that every 4-connected plane triangulation with n vertices can be redrawn with straight edges and all vertices lying on at most sqrt(2n) horizontal or vertical lines. The proof builds on a new result about drawing planar lattice diagrams on few lines, using orthogonal chain and antichain families.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproved visibility invariant in the final stage of Theorem 6: newly inserted chain vertices are asserted to be convex, but additional edges to both boundary chains can make them reflex, so the stretch argument is not secured.","rationale":"The core lattice-theoretic ingredients (Corollary 1, Lemmas 1 and 2) are standard, and the reduction from transversal structures to planar lattices is plausible. The main theorem would follow if every 4-connected triangulation admits the stated reduction and if Theorem 6 is correct. The weak point is the geometric shelling in §3, exactly as the reader identifies. The invariant is not a minor technicality: it is the mechanism that lets the proof place arbitrary remaining components inside faces after the two boundary drawings Λ' and Λ'' have been combined. The sentence 'each new element contributes convex corners in all incident faces' is doing the work, and it is not derived from the construction. In particular, a vertex of C can have edges to both boundary chains, so the face incident to that vertex is subdivided and the vertex need not be flat; whether the resulting angles are all convex depends on the cyclic order of edges and on the height function h, and the manuscript gives no argument. If the invariant fails, horizontal stretching does not guarantee that the segment connecting p and q lies inside F_B, and crossings can occur. I also note that the lower-bound remark after Theorem 1 is underived, but it does not affect the upper bound. The proposed check—an angle and cyclic-order computation at the chain-insertion operation—would either produce a counterexample or force the missing proof; until then CONDITIONAL is the right verdict.","tokens_in":11732,"tokens_out":17051,"duration_ms":183416,"concrete_test":"Formalize the final phase of Theorem 6 as a lemma and prove it by induction over the three operations: left-ear insertion, right-ear insertion, and chain insertion with additional edges to δ' and δ''. At the chain-insertion step, take an internal vertex v of C, list the cyclic order of incident edges (the two C-edges and the edges to δ' and δ''), and compute the interior angle of each face created. Check whether every such angle is ≤π; if a reflex angle is realizable by a planar lattice with the prescribed height h, the invariant fails and the 'big ear' placement can cross, while if all angles are ≤π, write the missing paragraph proving it. This settles the only unproved load-bearing geometric assertion in §3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 6 rests, in its last phase, on the invariant stated for each face F of the partial drawing Λ: if a segment between two boundary points of F is not contained in the interior of F, then the obstructing boundary parts belong to the outer chains γ' or γ''. The invariant is used twice: to place a remaining chain C inside a face F_B after a horizontal stretch, and to conclude in the same-side case that the segment connecting p and q lies inside F_B once the drawing is stretched. The text justifies the invariant with the sentence 'each new element contributes convex corners in all incident faces,' but this is not established. An internal vertex v of C has two collinear C-edges, and the proof explicitly allows additional edges from v to both δ' and δ''. Those additional edges subdivide F_B, and the interior angle at v in one of the resulting faces can be reflex; for instance, if the edges to δ' and δ'' leave v on the side of the face being considered, the boundary at v consists of a C-edge and both extra edges in a cyclic order that may give an interior angle greater than π. The text gives no argument ruling this out. No induction is given for how the invariant survives ear additions, chain insertions with additional edges, and the affine embedding of the 'big ear' component; the statement 'the invariant holds' carries the entire final phase. If the invariant fails, the recursive placement of remaining chains can introduce crossings, and Theorem 6 is not proved by the current text. The lower-bound remark after Theorem 1 is also asserted without derivation, but it is not load-bearing for the main claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 1: every 4-connected plane triangulation on n vertices admits a plane straight-line drawing whose vertices lie on at most sqrt(2n) horizontal or vertical lines, with the same conclusion claimed for subgraphs of such triangulations. The proof chain is: transversal structures on internally 4-connected triangulations give a red bipolar orientation that is the diagram of a planar lattice; Frank's orthogonal chain/antichain theory (Corollary 1) gives a cover by k antichains and ell chains with k + ell at most sqrt(2n) - 1; Lemmas 1 and 2 replace the pair by a canonical one; Proposition 4 gives drawings with prescribed heights and a vertical boundary chain; and Theorem 6 assembles these ingredients by an ear-shelling construction. Theorem 7 adds the blue edges of the transversal structure, and Theorem 1 follows by deleting an outer edge, drawing with infinite heights for the two poles, and reconnecting them by vertical rays.","tokens_in":1501,"tokens_out":1430,"duration_ms":262898,"significance":"If the proof is completed, this is a significant advance: it gives a sublinear upper bound on the line cover number for the broad class of 4-connected plane triangulations and all their subgraphs, complementing Eppstein's Omega(n^{1/3}) lower-bound examples and the known NP-hardness for the case of two lines. The derivation up to Corollary 1 is clean and parameter-free, the canonicalization in Lemmas 1 and 2 is convincing, and Proposition 4 is a useful standalone tool. The main risk is the final recursive stage of Theorem 6, where the crossing-free placement of remaining components and the inclusion of blue edges rely on a visibility invariant that is stated and asserted rather than proved; this is the load-bearing point that needs a complete argument before the central claim is fully established.","major_comments":[{"comment":"The visibility invariant is load-bearing but not proved. The text states that for each face F and two boundary points x,y, if the segment xy is not in the interior of F, then the obstructing boundary parts belong to gamma' or gamma'', and justifies it by saying that 'each new element contributes convex corners in all incident faces.' This is not a complete argument: an internal vertex of an inserted chain C is incident to two collinear C-edges and, as the text explicitly allows, to several additional edges to delta' and delta''. One must prove that the cyclic order of these edges around such a vertex keeps every incident face angle at most pi and that this local convexity implies the global statement about obstructing segments. No induction is given for how the invariant survives ear additions, chain insertions with additional edges, and the affine embedding of the big-ear component. Since the same-side case and the later blue-edge insertion in Section 4 both invoke this invariant, the proof of Theorem 6 is incomplete as written.","section":"Section 3, final paragraphs of Theorem 6"},{"comment":"The assertion 'Since gamma' and gamma'' do not admit ear extensions we know that not both of p and q belong to one of gamma' and gamma''' is unproved. This is the exact point where the segment zeta connecting the minimum and maximum of the chosen chain could lie on the boundary rather than in the interior of the face, and the argument needs to rule that out. The text relies on this claim to conclude that a sufficient horizontal stretch puts zeta inside F. Without a proof of the claim, the same-side case is not closed.","section":"Section 3, same-side case in the final stage of Theorem 6"},{"comment":"The recursive step says that 'we will repeat the choice of a component B and a chain C from B' with the property that the minimum and maximum of C have connecting edges to the two sides of the face F_B, but no proof is given that such a chain always exists, that the process terminates, or that the final alternative ('B is kind of a big ear over zeta_B') exhausts all possibilities. The correctness of the whole construction depends on this exhaustion, so a precise argument is needed.","section":"Section 3, recursive choice of components and chains"}],"minor_comments":[{"comment":"The statement that Eppstein's graph G_ell can be extended to a 4-connected plane triangulation with only O(ell^3) vertices, yielding pi(G) in Omega(n^{1/3}), is asserted without proof or construction details. Since the introduction uses this to claim near-optimality, a proof or a precise reference would be appropriate.","section":"Section 1, lower-bound remark"},{"comment":"The use of h(s) = -infinity and h(t) = infinity is informal, since h was defined as a real-valued extension in Section 3. The passage from finite drawings to vertical rays and then to finite edges ending at ps and pt should be justified by a limiting or compactness argument.","section":"Section 4, proof of Theorem 1"},{"comment":"The phrase 'The same holds for all subgraphs of such triangulations' is ambiguous: if the subgraph has fewer vertices than the ambient triangulation, the bound sqrt(2n) should specify whether n is the number of vertices of the subgraph or of the triangulation, since the proof only directly gives the latter.","section":"Abstract and introduction"},{"comment":"There are several minor typographical issues (for example, 'Therfore' and 'sufficient'), and the references should be checked for completeness and formatting consistency.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The core idea is original and the early parts of the proof are solid, but the final stage of Theorem 6 is too sketchy for a journal version. The gaps appear fixable rather than fatal, so I recommend major revision rather than rejection. The author should be asked to provide a complete proof of the visibility invariant and of the termination/exhaustion of the recursive placement, and to clarify the subgraph claim in the abstract."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper: it proves that every 4-connected plane triangulation on n vertices can be redrawn with straight edges and all vertices covered by at most sqrt(2n) horizontal or vertical lines, and the same for subgraphs. That bound is new, and the route through planar lattice diagrams, Greene-Kleitman theory, and Frank's orthogonal chain/antichain pairs is genuinely different from the existing stacked-triangulation and lower-bound work. The core derivation up to the ear-shelling is clean: Corollary 1 gives the orthogonal pair with k+ell <= sqrt(2n)-1, and Lemmas 1 and 2 canonicalize the chain and antichain families in a way that fits the drawing construction. The result is a solid subfield contribution, not a breakthrough, but it closes part of the gap against Eppstein's Omega(n^{1/3}) lower bound and leaves the right open question for all planar graphs.\n\nThe soft spot is the final stage of Theorem 6. The visibility invariant — that any segment obstructed inside a face is blocked only by the outer chains gamma' or gamma'' — is stated, used to place remaining chains, and justified with a single sentence: \"each new element contributes convex corners in all incident faces.\" The stress-test worry is that an internal chain vertex with extra edges to both boundary chains could create a reflex corner, breaking the invariant. I read that as a legitimate concern about the exposition, not a clear counterexample. Because the chain edges are collinear and all other edges attach from strictly opposite half-planes, the interior angles at the new vertices should still be at most pi after a short argument; but the paper does not supply that argument, and the invariant carries a lot of weight. This is fixable, but as written it is a gap.\n\nThe Omega(n^{1/3}) remark after Theorem 1 is also asserted without derivation. It is not load-bearing for the main theorem, so that is minor.\n\nWho gets value: graph drawing researchers and anyone working on line/plane cover numbers; the poset theory audience will also appreciate the orthogonal-pair technique. I would send this to a serious referee. The result is new, the proof idea is worth publishing, and the gaps are repairable rather than fatal. A revision should expand the proof of the visibility invariant and add at least a sketch or reference for the lower-bound construction.","headline":"New O(sqrt n) line-cover bound for 4-connected triangulations via orthogonal pairs and planar lattice diagrams; main theorem likely correct, but the proof of Theorem 6 has a genuine expository gap in the final visibility invariant.","tokens_in":12570,"tokens_out":5592,"would_cite":true,"duration_ms":56033,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","06A07"],"pacs":[],"model":"deepseek-v4-flash","headline":"4-connected plane triangulations on $n$ vertices admit straight-line drawings whose vertices lie on at most $\\sqrt{2n}$ horizontal or vertical lines, and every subgraph inherits the bound.","keywords":["graph drawing","line cover number","4-connected triangulations","transversal structures","planar lattices","orthogonal chain-antichain families","poset dimension","straight-line drawings"],"falsifier":"A concrete check is to run the recursive drawing procedure for a small planar lattice or a small 4-connected triangulation and, after each ear-shelling step, inspect every face for a straight segment between two boundary points that is blocked by a boundary vertex outside the two designated outer chains; finding such a face would falsify the proof's invariant, whereas computing $\\pi(G)>\\sqrt{2n}$ for a 4-connected triangulation would refute the theorem itself.","tokens_in":11520,"feed_emoji":"📐","tokens_out":13633,"duration_ms":127090,"temperature":0.7,"pith_summary":"For a plane graph $G$, the line cover number $\\pi(G)$ is the minimum number of straight lines needed to cover all vertices of some plane straight-line drawing. This paper proves that every 4-connected plane triangulation on $n$ vertices has $\\pi(G) \\le \\sqrt{2n}$, and that the covering lines can be chosen horizontal or vertical. The proof goes through a planar lattice: the red part of a transversal structure is the diagram of a planar lattice, which is drawn on the union of $k$ horizontal antichain levels and $\\ell$ vertical chains with $k+\\ell \\le \\sqrt{2n}-1$, and the remaining edges are inserted afterwards. The same drawing covers every subgraph. A companion construction shows the result is not far from optimal: there are 4-connected triangulations whose line cover number grows like $\\Omega(n^{1/3})$.","feed_headline":"4-connected triangulations fit on sqrt(2n) lines","feed_subtitle":"A lattice-diagram proof covers every vertex by horizontal or vertical lines; subgraphs inherit the drawing.","key_machinery":"The load-bearing object is a transversal structure: an orientation and red/blue coloring of the inner edges of an internally 4-connected inner triangulation such that at each inner vertex the four color-and-direction classes form four cyclic blocks. The red subgraph, with the four outer directions added, is the diagram of a planar lattice. The proof covers the elements of this lattice by an orthogonal pair $(\\mathcal{A},\\mathcal{C})$: a $k$-antichain and an $\\ell$-chain whose members together cover the poset and any chain intersects any antichain in exactly one element, with $k+\\ell \\le \\sqrt{2n}-1$; the existence of such a pair follows from the chain–antichain partition theory of posets. The elements of $\\mathcal{A}$ become horizontal levels and the chains of $\\mathcal{C}$ become vertical lines, giving the few-line drawing of the lattice diagram; the remaining edges are then inserted inside faces, with the blue edges added during the same shelling process.","core_discovery":"The central result, Theorem 1, states that if $G$ is a 4-connected plane triangulation on $n$ vertices, then $\\pi(G) \\le \\sqrt{2n}$. The proof establishes the stronger Theorem 7: an internally 4-connected inner triangulation of a 4-gon on $n$ vertices has a plane straight-line drawing with all vertices on at most $\\sqrt{2n}-1$ lines, each horizontal or vertical, and with every crossing point of a horizontal and a vertical line occupied by a vertex. Deleting one outer edge of a 4-connected triangulation yields such a triangulation, and the two removed vertices can be placed on one additional vertical line, yielding Theorem 1. Because the drawing is of the full triangulation, every subgraph is drawn on the same set of lines.","pith_inferences":["The same orthogonal-pair mechanism could plausibly give $O(\\sqrt{n})$-line drawings for other graph classes with a red/blue decomposition, such as 5-connected triangulations or triangulations with separating triangles, provided their red subgraph yields a planar lattice or a comparable drawing-friendly poset.","The asserted visibility invariant is the step to check first: if it fails on some instance, the proof of the lattice-drawing theorem needs repair even though the statement of the main theorem might still be true.","The gap between the $\\Omega(n^{1/3})$ lower bound and the $\\sqrt{2n}$ upper bound leaves the true worst-case exponent open, so computing the line-cover number for small 4-connected triangulations could suggest whether the extremal behavior is closer to $n^{1/3}$ or to $\\sqrt{n}$."],"forward_implications":["Every 4-connected plane triangulation on $n$ vertices has a plane straight-line drawing whose vertices are covered by at most $\\sqrt{2n}$ horizontal or vertical lines, and every subgraph has such a drawing on the same line set.","The drawings can be produced in polynomial time, because the transversal structure, the orthogonal pair, and the ear-shelling steps are all constructive.","There exist 4-connected plane triangulations whose line cover number is $\\Omega(n^{1/3})$, so the worst-case exponent lies somewhere between $1/3$ and $1/2$.","For internally 4-connected inner triangulations of a 4-gon, the constructed drawing has the extra rigidity that every crossing point of a horizontal and a vertical line is occupied by a vertex."],"supporting_citations":[{"why":"Supplies the existence of orthogonal chain–antichain families, the basis of Corollary 1.","marker":"[11]"},{"why":"Provides the dual chain/antichain min–max theorem used to obtain the orthogonal pair with the desired size bound.","marker":"[15]"},{"why":"Supplies the k-antichain/chain partition min–max theorem that underlies the orthogonal-pair counting.","marker":"[16]"},{"why":"Establishes that the red and blue graphs of a transversal structure are bipolar orientations, so the red graph is a planar lattice diagram.","marker":"[17]"},{"why":"Shows every internally 4-connected inner triangulation of a 4-gon admits a transversal structure and uses it for straight-line drawings.","marker":"[13]"}],"fun_headline_variants":["4-connected triangulations draw on sqrt(2n) lines","Every 4-connected triangulation fits on sqrt(2n) lines","4-connected triangulations: all vertices on sqrt(2n) lines","sqrt(2n) axis-aligned lines cover 4-connected triangulations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction in the final ear-shelling stage depends on an invariant that is asserted rather than proved: inside each face of the partial drawing, a straight segment between two boundary points is obstructed only by boundary vertices on the two designated outer chains, and if this fails the recursive placement of remaining chains could create crossings.","fun_headline_variants_meta":{"raw":{"variants":["4-connected triangulations draw on sqrt(2n) lines","Every 4-connected triangulation fits on sqrt(2n) lines","4-connected triangulations: all vertices on sqrt(2n) lines","sqrt(2n) axis-aligned lines cover 4-connected triangulations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001583,"raw_usage":{"total_tokens":6222,"prompt_tokens":761,"completion_tokens":5461,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":377,"completion_tokens_details":{"reasoning_tokens":5392}},"tokens_in":377,"tokens_out":5461,"duration_ms":38735,"temperature":1.0,"reasoning_tokens":5392,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:41:05.686628+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check is to run the recursive drawing procedure for a small planar lattice or a small 4-connected triangulation and, after each ear-shelling step, inspect every face for a straight segment between two boundary points that is blocked by a boundary vertex outside the two designated outer chains; finding such a face would falsify the proof's invariant, whereas computing $\\pi(G)>\\sqrt{2n}$ for a 4-connected triangulation would refute the theorem itself.","supporting_citations":[{"cited_title":"Frank , On chain and antichain families of partially ordered sets , J","cited_arxiv_id":null,"evidence_quote":"Supplies the existence of orthogonal chain–antichain families, the basis of Corollary 1."},{"cited_title":"Greene , Some partitions associated with a partially ordered set , J","cited_arxiv_id":null,"evidence_quote":"Provides the dual chain/antichain min–max theorem used to obtain the orthogonal pair with the desired size bound."},{"cited_title":"Greene and D","cited_arxiv_id":null,"evidence_quote":"Supplies the k-antichain/chain partition min–max theorem that underlies the orthogonal-pair counting."},{"cited_title":"Kant and X","cited_arxiv_id":null,"evidence_quote":"Establishes that the red and blue graphs of a transversal structure are bipolar orientations, so the red graph is a planar lattice diagram."},{"cited_title":"Fusy , Transversal structures on triangulations: A combinatorial study and straight-line drawings , Discr","cited_arxiv_id":null,"evidence_quote":"Shows every internally 4-connected inner triangulation of a 4-gon admits a transversal structure and uses it for straight-line drawings."}],"review_version":1}