{"id":"9daf8e8b-4a1c-45c1-a79b-699457fe240b","arxiv_id":"1908.03586","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The planar edge-length ratio of n-vertex planar graphs can be Theta(n), 2-trees admit an O(n^0.695) upper bound, and bipartite planar graphs approach ratio 1.","lead":"This paper proves that some planar graphs force drawings whose longest edge is linearly longer than the shortest edge, and that this is the worst possible case. It also shows that many series-parallel and bipartite graphs can be drawn with nearly uniform edge lengths.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's proof is built on a false reduction: K_{1,m} cannot be augmented to a maximal bipartite planar graph by adding edges only, so the induction over maximal quadrangulations does not cover all bipartite planar graphs.","rationale":"The reader's weakest assumption already identified the augmentation failure for K_{1,m}, and my independent check of Section 4.3 confirms it. I do not find a comparable flaw in Theorem 1 or Theorem 3. The Chan inequality quoted in Theorem 3 is verifiable: for alpha=log_2 phi, (1/2)^alpha+(1/4)^alpha = 1/phi + 1/phi^2 = 1, so the boundary case x=n/2, y=n/4 is tight, and concavity of u^alpha+v^alpha handles the rest of the constraint polygon. The decomposition lemma's counting appears sound, and L2T-drawer's geometric inequalities check out. Theorem 1's induction with gamma=0.3 is plausible, and the angle cases in Lemmata 2 and 3 are consistent with the stated configurations. Thus the only serious defect I find is the false reduction in Theorem 4. Since the theorem is likely repairable and the other central results appear correct, the appropriate outcome remains CONDITIONAL, matching the reader's verdict.","tokens_in":16364,"tokens_out":34670,"duration_ms":375448,"concrete_test":"Check the proof of Theorem 4 against G=K_{1,4}. Attempt to construct a maximal bipartite planar supergraph on the same five vertices: since all four leaves form one bipartition class, any added edge among leaves makes the graph non-bipartite, and all center-leaf edges are already present. No such augmentation exists, so the reduction 'by adding edges' fails. A corrected proof would need either to add vertices before taking a maximal quadrangulation, or to give a separate drawing of stars, which trivially have ratio 1. If the paper's text is amended accordingly, the theorem may stand; as written, the induction has a gap at this reduction step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim includes the statement that every bipartite planar graph has planar edge-length ratio below 1+epsilon (Theorem 4, Section 4.3). The first step of the proof asserts that it suffices to consider maximal bipartite planar graphs, because any nonmaximal bipartite planar graph can be augmented to a maximal one by adding edges. This is false. Let G=K_{1,m} with m>=3. The bipartition of a connected bipartite graph is unique up to swapping the parts: the center is one part and all leaves are the other. No edge can be added between two leaves without creating an odd cycle in the same part, and no other edge is absent. Hence no edge-maximal bipartite planar supergraph on the same vertex set exists. Therefore the reduction in Section 4.3 does not apply to stars, and the theorem is not established for them by the given induction. The statement itself is plausible and a fix may exist, e.g., by adding new vertices to obtain a quadrangulation or by handling non-maximal graphs directly, but the paper does not supply that argument. This is a load-bearing gap because the bipartite result is one of the advertised results, not a peripheral remark.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the planar edge-length ratio of planar graphs, defined as the minimum over planar straight-line drawings of the ratio between the longest and shortest edge lengths. It proves an Omega(n) lower bound for infinitely many n-vertex planar graphs and notes that this is tight because every planar graph admits an O(n) by O(n) grid drawing. For upper bounds, the paper proves that plane 3-trees of depth k have planar edge-length ratio O(k), that every n-vertex 2-tree (and hence every n-vertex graph of treewidth at most 2) has planar edge-length ratio O(n^{log_2 phi}) with log_2 phi < 0.695, and that every bipartite planar graph has planar edge-length ratio below 1+epsilon. The lower-bound proof uses a concrete family of nested plane 3-trees and two perimeter-growth lemmas; the 2-tree result uses a decomposition into a linear 2-tree plus small components, following a technique of Chan; the bipartite result uses the inductive generation of maximal bipartite plane graphs by operations P0 and P1.","tokens_in":16553,"tokens_out":22485,"duration_ms":248861,"significance":"If the results are established, this is a substantial contribution to a recently active area. The linear lower bound answers the natural order-of-magnitude question for general planar graphs, and the sublinear upper bound for 2-trees provides a sharp counterpart to the Omega(log n) lower bound of Blazek et al. The plane 3-tree depth bound and the near-1 bound for bipartite planar graphs are also strong. The paper is careful in its explicit geometric arguments, particularly the perimeter lemmas and the concrete nested-triangle construction. However, the proof of Theorem 4 contains a false reduction at its first step, and this is load-bearing for one of the advertised results; the paper therefore cannot be accepted in its present form.","major_comments":[{"comment":"The reduction to maximal bipartite planar graphs is false. For G = K_{1,m} with m >= 3, the bipartition is unique: the center forms one part and all leaves form the other. No edge can be added between two leaves without placing two vertices in the same part, and every possible edge from the center is already present. Hence no edge-maximal bipartite planar supergraph on the same vertex set exists, and in particular G cannot be augmented to the plane quadrangulations used in the induction based on the operations P0 and P1 of Brinkmann et al. The remaining proof only handles maximal bipartite plane graphs that are quadrangulations, so Theorem 4 is not established for stars or, more generally, for non-quadrangulated bipartite planar graphs. The claim may be repairable, for instance by proving that every bipartite planar graph is a subgraph of a maximal bipartite planar graph on a superset of vertices (K_{1,m} is a subgraph of K_{2,m}) and then applying Lemma 1, but that argument is not present and must be supplied.","section":"Section 4.3, proof of Theorem 4, first paragraph"}],"minor_comments":[{"comment":"The proof asserts that x, y, and z are all at least 1, but z can be 0 when H contains no class 1-2 edge other than the root; the 3-vertex 2-tree is an example. The argument is salvageable by defining f(0) = 0 and relaxing the input condition of L2T-drawer for edge classes that do not occur in H, but the text should be corrected.","section":"Section 4.2, proof of Theorem 3"},{"comment":"The inequality f(n) >= f(x) + f(y) is quoted from Chan [5] without stating the result itself. Since the sublinear exponent depends on this inequality, it would improve the paper to state the lemma explicitly together with the exact hypotheses under which it applies.","section":"Section 4.2, Theorem 3"},{"comment":"After the augmentation step is fixed, the phrase 'maximal bipartite planar graph' should be clarified, because the term is used differently in the edge-maximal sense and in the sense of plane quadrangulations used by Brinkmann et al.; the current transition between the two meanings is a source of the gap described in the major comment.","section":"Section 4.3, proof of Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the scope of a journal in graph drawing and discrete mathematics. The only decisive issue I found is the false augmentation claim in Theorem 4; if the authors supply a correct reduction, the paper is likely acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth knowing: this paper settles the worst-case planar edge-length ratio at Theta(n), and it gives the first sublinear upper bound, O(n^0.695), for treewidth-2 graphs. Those two results are solid and are the reason to read it. The bipartite claim (ratio below 1+epsilon) is plausible, but the proof as written does not cover all bipartite planar graphs.\n\nWhat's new: the lower-bound construction is a nested-triangle 3-tree with a careful perimeter-growth argument, and it is genuinely nontrivial—many standard lower-bound gadgets have constant ratio. The 2-tree result combines a linear-2-tree drawing algorithm with a decomposition lemma that controls component sizes; the exponent log_2 phi comes out of the recurrence, and the Chan inequality is cited properly. This makes a nice counterpart to Blazej et al.'s Omega(log n) lower bound.\n\nSoft spots: the proof of Theorem 4 opens by asserting that any nonmaximal bipartite planar graph can be augmented to a maximal one by adding edges. That is false for K_{1,m}: the bipartition is forced, no leaf-leaf edge can be added, and all center-leaf edges are already present. If \"maximal\" means quadrangulation, then K_{1,m} is not maximal and cannot be made one by edge additions alone; if \"maximal\" means edge-maximal with respect to bipartiteness, then the Brinkmann et al. generation theorem does not apply to it. Either way, the reduction to maximal quadrangulations does not cover stars or other non-2-connected graphs. The theorem itself may be true—stars have ratio 1, and one could augment by adding vertices before applying induction—but the paper does not supply that argument. This is a load-bearing gap in an advertised result, though probably fixable.\n\nI also note that Theorem 3 rests on Chan's inequality as a black box; that is acceptable since it is in the literature, but the sublinear exponent depends on it. The lower-bound geometry and the plane 3-tree invariant are detailed and check out. No circular reasoning; gamma is an internal proof parameter.\n\nWho it is for: graph drawing people working on edge-length aesthetics, and anyone tracking open problems on 2-trees. It deserves a serious referee. My recommendation: send it out, but require the bipartite proof to be repaired, either by handling nonmaximal graphs directly or by augmenting with new vertices and using subgraph monotonicity.","headline":"Settles the planar edge-length ratio at Theta(n) and gives the first sublinear bound for treewidth-2 graphs, but the bipartite theorem's proof has a false augmentation step that needs a fix.","tokens_in":17096,"tokens_out":5410,"would_cite":true,"duration_ms":59045,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Some planar graphs force edge-length ratios that grow linearly with n, while treewidth-2 graphs always have sublinear ratio.","keywords":["edge-length ratio","planar graph drawing","2-trees","treewidth","series-parallel graphs","bipartite planar graphs","plane 3-trees","golden ratio"],"falsifier":"Test the first reduction of the bipartite theorem on the star $K_{1,3}$: no edge additions can turn it into a maximal bipartite planar graph without adding vertices or changing the bipartition, so the proof's reduction is invalid for this input and the argument must be repaired there.","tokens_in":16131,"feed_emoji":"📐","tokens_out":15633,"duration_ms":151764,"temperature":0.7,"pith_summary":"Every $n$-vertex planar graph has a straight-line drawing on an $O(n)\\times O(n)$ grid, so no drawing needs an edge-length ratio worse than $O(n)$. This paper shows that some $n$-vertex planar graphs actually require a ratio of $\\Omega(n)$, making the linear bound tight. It also proves that every graph of treewidth at most two—including 2-trees and series-parallel graphs—can be drawn with planar edge-length ratio $O(n^{\\log_2\\varphi})\\subseteq O(n^{0.695})$, where $\\varphi$ is the golden ratio, and that every bipartite planar graph can be drawn with ratio arbitrarily close to $1$. Along the way it shows plane 3-trees (maximal planar graphs built by inserting vertices into triangular faces) have ratio proportional to their depth. The concrete upshot is a sharp worst-case picture: sublinear ratio for treewidth 2, linear ratio starting at treewidth 3.","feed_headline":"Some planar graphs force edge ratios that grow linearly with n","feed_subtitle":"Treewidth-2 graphs draw with sublinear edge-length ratio; bipartite planar graphs approach ratio 1.","key_machinery":"The load-bearing construction for the treewidth-2 bound is the linear 2-tree decomposition: every 2-tree contains a linear 2-tree subgraph $H$, drawn by the L2T-drawer algorithm, which assigns vertices three colour classes and guarantees that every edge of class 1-2, 1-3, or 2-3 has length at least a prescribed value. Removing $H$ splits the graph into $H$-components whose largest sizes $x,y,z$ satisfy $z\\le n/2$ and either $x\\le n/2$ with $y\\le (n-x)/2$, or symmetrically. The recursion uses $f(n)=n^{\\log_2\\varphi}$, with the defining property that $f(n)\\ge f(x)+f(y)$ holds under exactly these balance conditions; the golden ratio enters because $1/\\varphi+1/\\varphi^2=1$ makes the inequality tight at $x=n/2$, $y=n/4$. For the lower bound, the machinery is a family of nested triangles $G_k$, where a perimeter-growth lemma forces the outer triangle's perimeter to increase by a constant at each of $k$ layers.","core_discovery":"The paper's central claim is that the planar edge-length ratio—the smallest possible ratio between the longest and shortest edge in a planar straight-line drawing—is controlled sharply by treewidth. For $n=6k-2$ it constructs a planar graph by gluing two copies of a nested-triangle plane 3-tree to a complete graph on four vertices, and proves any planar drawing of it has ratio $\\Omega(n)$; since an $O(n)\\times O(n)$ grid drawing gives ratio $O(n)$ for every planar graph, this is tight. For graphs with treewidth at most two, it proves a sublinear upper bound $\\rho(G)\\in O(n^{\\log_2\\varphi})$ with $\\varphi=(1+\\sqrt{5})/2$, by decomposing any 2-tree into a linear 2-tree spine whose removal leaves small components, drawing the spine with prescribed edge-length classes, and recursing. It also proves that plane 3-trees of depth $k$ have ratio $O(k)$, and that every bipartite planar graph has ratio below $1+\\varepsilon$ for any $\\varepsilon>0$.","pith_inferences":["Beyond the paper's own claims: because the golden-ratio inequality is tight at component sizes $x=n/2$ and $y=n/4$, the exponent $\\log_2\\varphi\\approx 0.695$ is likely the best this decomposition can deliver; improving the bound would require a stronger decomposition lemma or a different drawing primitive, neither of which the paper proposes.","Also editorial: the bipartite proof's first reduction—augmenting to a maximal bipartite planar graph by adding edges—fails for stars such as $K_{1,3}$; since stars themselves have ratio $1$, the theorem may still be true, but the proof needs a repair such as allowing added vertices or a separate base case.","A natural next test is whether the spine decomposition generalizes to graphs of bounded treewidth $k$, with the exponent governed by a generalized balance equation that would interpolate between $0.695$ and $1$; the paper does not attempt this generalization."],"forward_implications":["The planar edge-length ratio of planar graphs is $\\Theta(n)$ in the worst case, so the standard $O(n)\\times O(n)$ grid drawing cannot be improved asymptotically on ratio grounds.","Every series-parallel graph, and more generally every treewidth-2 graph, admits a planar straight-line drawing with edge-length ratio $O(n^{0.695})$.","Bipartite planar graphs have planar edge-length ratio approaching $1$, so their edges can be made nearly uniform in length.","The lower-bound graphs have treewidth 3, so the transition from sublinear to linear planar edge-length ratio is sharp at treewidth 3 within these families.","If crossings are allowed but vertex-edge overlaps are forbidden, planar graphs have edge-length ratio $O(1)$ by combining the paper's chromatic-number result with the four-colour theorem, in contrast to the linear lower bound for planar drawings."],"supporting_citations":[{"why":"Supplies the black-box inequality $f(n)=n^{\\log_2\\varphi}\\ge f(x)+f(y)$ that the recursive 2-tree drawing scheme invokes for component sizes satisfying Lemma 4.","marker":"[5]"},{"why":"Provide the $O(n)\\times O(n)$ grid-drawing theorems that yield the matching $O(n)$ upper bound for the $\\Omega(n)$ lower bound.","marker":"[6,14]"},{"why":"Gives the generation of maximal bipartite plane graphs by the operations P0 and P1, which is the inductive skeleton of Theorem 4.","marker":"[3]"},{"why":"Supplies the continuity and vertex-expansion principle used to insert one new vertex inside an $\\varepsilon$-disk in the bipartite induction.","marker":"[9]"}],"fun_headline_variants":["Some planar graphs force edge-length ratio linear in n","Treewidth-2 planar graphs have sublinear edge-length ratio","Bipartite planar graphs have edge-length ratio near 1","Planar edge-length ratio: linear for some, near 1 for bipartite"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Two borrowed assumptions carry the sharpest results: the 2-tree bound assumes the golden-ratio inequality $f(n)\\ge f(x)+f(y)$ holds for every component-size pair produced by the decomposition, and the bipartite bound assumes every bipartite planar graph can be made maximal bipartite planar by adding only edges—a step that fails for a star with at least three leaves.","fun_headline_variants_meta":{"raw":{"variants":["Some planar graphs force edge-length ratio linear in n","Treewidth-2 planar graphs have sublinear edge-length ratio","Bipartite planar graphs have edge-length ratio near 1","Planar edge-length ratio: linear for some, near 1 for bipartite"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001241,"raw_usage":{"total_tokens":5055,"prompt_tokens":868,"completion_tokens":4187,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":4114}},"tokens_in":484,"tokens_out":4187,"duration_ms":30725,"temperature":1.0,"reasoning_tokens":4114,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:10:51.040964+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test the first reduction of the bipartite theorem on the star $K_{1,3}$: no edge additions can turn it into a maximal bipartite planar graph without adding vertices or changing the bipartition, so the proof's reduction is invalid for this input and the argument must be repaired there.","supporting_citations":[{"cited_title":"Algorithmica 34(1), 1–13 (2002)","cited_arxiv_id":null,"evidence_quote":"Supplies the black-box inequality $f(n)=n^{\\log_2\\varphi}\\ge f(x)+f(y)$ that the recursive 2-tree drawing scheme invokes for component sizes satisfying Lemma 4."},{"cited_title":"Discrete Mathematics 305(1-3), 33–54 (2005)","cited_arxiv_id":null,"evidence_quote":"Gives the generation of maximal bipartite plane graphs by the operations P0 and P1, which is the inductive skeleton of Theorem 4."},{"cited_title":"Acta Sci","cited_arxiv_id":null,"evidence_quote":"Supplies the continuity and vertex-expansion principle used to insert one new vertex inside an $\\varepsilon$-disk in the bipartite induction."}],"review_version":1}