{"id":"7ac37b69-da48-4683-a647-ef6a4108cebf","arxiv_id":"1908.06688","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A simple priority-based shelling heuristic produces well balanced Schnyder woods in practice, and experiments suggest these improve Schnyder drawing quality and cycle separator size.","lead":"This paper introduces a fast heuristic that balances the three color classes of Schnyder woods on planar triangulations. Experiments on real and random meshes suggest the balanced woods yield nicer straight-line drawings and shorter cycle separators, though without worst-case guarantees.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Fig. 3 experiment conflates balance with other structural changes from random triangle reversals, so the causal role of balance in quality gains is not established.","rationale":"The central claim is an empirical causal one: balanced Schnyder woods cause better drawings and separators. The only evidence designed to isolate balance is Fig. 3, where random reversals of ccw triangles produce a sequence of woods with increasing δavg. This manipulation simultaneously changes multiple structural properties: the orientation of every reversed face, the lengths and winding of the paths P_i(v), and the spatial distribution of cw/ccw faces. δavg is a one-dimensional summary of the degree distribution at vertices; it cannot distinguish among these co-varying factors. The heuristic itself is guided by an incoming-edge priority, not by δ0/δavg, so the good performance of the heuristic might be due to the shelling order producing short paths, with balance only a side effect. If so, the paper's contribution is not about balance, and the title and abstract overstate the role of the balanced property. This is not an accusation of error; it is an honest gap in the experimental design, and the manuscript never acknowledges or tests the confound. The proposed test would settle it: grouping woods by δavg and comparing quality within groups, or partialling out structural covariates, would show whether δavg has an independent effect. Because this is a concrete, addressable experimental gap rather than a proof of falsehood, the conditional verdict (accept with revisions) remains appropriate; no change from the reader's verdict is needed.","tokens_in":9609,"tokens_out":9948,"duration_ms":92990,"concrete_test":"On a subset of the real-world meshes (e.g., horse, Egea, sphere), generate for each graph multiple Schnyder woods at the same target δavg by applying different random sequences of ccw-triangle reversals to the heuristic wood, and also by re-running the heuristic with randomized tie-breaking. Measure the edge-length metric el and separator size within each δavg group; if the within-group variance is comparable to the between-group differences, the effect attributed to balance in Fig. 3 fails a direct causal test. Additionally, compute the partial correlation of el with δavg controlling for the number of ccw triangles and the average length of the three paths P_i(v), and require the partial correlation to remain significantly negative to support the balance hypothesis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that balanced Schnyder woods improve drawing quality and separator size. The only evidence isolating balance is Fig. 3, which starts from a heuristic-produced balanced wood and randomly reverses ccw-oriented triangles to obtain a sequence with increasing δavg. This operation changes not only the balance metric but also the full orientation pattern, the lengths and winding of the three paths P_i(v), and the number and location of ccw faces. Since δavg is a one-dimensional summary that covaries with these structural changes, the monotone trend in Fig. 3 does not establish that balance per se causes the improvement; the heuristic's shelling order could be producing short paths and good layouts independently of balance, with balance as a correlated byproduct. The manuscript does not acknowledge or test this confound, despite the heuristic's priority rule being based on incoming-edge counts rather than δ0/δavg directly. This concern is load-bearing because if balance is not the active ingredient, the 'balanced Schnyder woods' framing of the paper is not supported by its experiments.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies balanced Schnyder woods for planar triangulations. It defines a vertex defect measure δ(v), global balance metrics δ0 and δavg, and proposes a linear-time heuristic based on a retarded vertex-conquest shelling procedure with k priority queues, optionally followed by a post-processing phase that reverses oriented triangles. The heuristic is used in two applications: Schnyder straight-line drawings, evaluated by the edge-length aesthetic metric, and simple cycle separators, evaluated by boundary size and partition balance. The experiments cover real-world meshes (aim@shape, Thingi10k), synthetic grids, random planar triangulations, and Delaunay triangulations, with hundreds of random seeds. The paper explicitly disclaims theoretical guarantees and claims only empirical evidence that balanced Schnyder woods improve layout quality and separator quality compared with minimal Schnyder woods.","tokens_in":9776,"tokens_out":5543,"duration_ms":61062,"significance":"If the empirical claim is correct, the paper offers a cheap and practical preprocessing step for two well-studied problems: higher-quality Schnyder drawings and short balanced cycle separators. The paper's strengths are the breadth of its test suite, the repetition over hundreds of seeds, the availability of datasets and code, and the honest framing that no worst-case guarantees are provided. The balance metric is computed independently of the heuristic's objective, and the separator selection scans all vertices, so there is no obvious fitting-to-target circularity. However, the causal link between balance and quality is not yet established: the experiment intended to isolate balance is confounded, and the comparisons lack statistical support. The contribution is therefore plausible and useful, but it needs strengthening before the abstract's causal wording is justified.","major_comments":[{"comment":"The experiment designed to isolate the effect of balance is confounded. Starting from a heuristic balanced wood and randomly reversing ccw-oriented triangles changes not only δavg but also the full orientation pattern, the three paths P_i(v) used by the drawing and separator routines, the number and location of ccw faces, and the region sizes Int(R_i(v)) on which separator balance is evaluated. Consequently, the monotone relationships in the middle and right charts of Fig. 3 could be driven by these correlated structural changes rather than by the balance defect itself. To support the paper's central claim, the manuscript should include a control that varies balance while holding other structural features roughly fixed (for example, comparing heuristic and minimal woods with matched δavg values, or performing a regression that includes path-length and ccw-face counts as covariates), or it should explicitly weaken the abstract's causal wording to a correlation statement.","section":"Section 2.3, Fig. 3"},{"comment":"The main empirical claims are reported without statistical tests or effect-size measures. The paper states conclusions such as \"our heuristic leads to well balanced Schnyder woods\" and \"the layout quality tends to deteriorate\" based on whisker plots, but no confidence intervals, standard errors, sample sizes per graph, or paired tests (e.g., Wilcoxon signed-rank over seeds) are given. Because the entire contribution is an empirical improvement claim, the authors should quantify the significance and magnitude of the differences between heuristic and minimal woods for balance, layout, and separator size.","section":"Section 2.3, Figs. 1, 3, 4, 6, 7"},{"comment":"The separator results are summarized with aggregate charts and a few per-graph labels, but the reader cannot determine how many seeds and graphs produced a valid α=2/3 separator or stayed under the √8m bound. Since the paper's second application is the claim that balanced woods provide an efficient tool for computing separators, the authors should report per-graph success rates and the distribution of boundary sizes (for instance, a table of medians and IQRs over seeds), and state explicitly whether every tested instance satisfied the stated bound.","section":"Section 2.3, Fig. 4"}],"minor_comments":[{"comment":"The abstract says \"planar graphs,\" but the paper actually studies planar triangulations; the terminology should be aligned throughout.","section":"Abstract and Section 2"},{"comment":"The notion \"well balanced if a majority of vertices have a small defect\" is not formalized; the authors should specify a threshold (e.g., δ(v) ≤ 1) or state the exact cutoff used in the plots.","section":"Section 2.1"},{"comment":"The runtime comparison against previous C implementations is not apples-to-apples: the present Java implementation runs on an i7-5600U with 1GB RAM, while the cited C implementations run on a Xeon X5650 with 48.4GB RAM. The authors should either run a controlled comparison on the same machine or explicitly label the comparison as indicative only.","section":"Section 2.3, Fig. 2"},{"comment":"The queue list is written as \"Q0, Q2, ..., Qk−1,\" which appears to omit Q1; it should be \"Q0, Q1, ..., Qk−1.\" In addition, the text mentions processing \"more than 3 M vertices per second\" for random triangulations, while Section 2.3 reports 1.43M–1.92M vertices per second; these numbers should be reconciled.","section":"Appendix A.2"},{"comment":"In the right chart, the axis labeled \"boundary size\" should state whether the value is normalized by √m, √n, or an absolute count; the caption lists √n, √m, √8n, and √8m without making the normalization explicit.","section":"Fig. 3"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern is the right one: Fig. 3 cannot bear the causal weight assigned to it. I would be willing to upgrade the recommendation if the authors add a matched control experiment (e.g., comparing woods with similar δavg produced by different constructions) and per-graph statistical summaries. The paper's experimental assets make such an extension feasible within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a serious look: it defines a balance measure for Schnyder woods, gives a simple linear-time priority-queue shelling heuristic, and runs the first broad experimental evaluation across real meshes, random triangulations, Delaunay, and synthetic grids. The code and data are available, timings are solid, and the claims are carefully hedged. That is real work, and it is honest work.\n\nWhat is actually new: the balance objective itself, the retarded conquest heuristic, and the experimental comparison against minimal Schnyder woods for drawing quality and cycle separators. The results on regular meshes are convincing that the heuristic produces more balanced woods (up to 79% balanced vertices on the sphere), and the paper does not try to sell theoretical guarantees it does not have. The runtime comparison with previous separator implementations is also fair and favorable.\n\nThe soft spots are real but not fatal. The Fig. 3 experiment is the main one: starting from a heuristic wood and randomly reversing ccw triangles changes not just δavg but the full orientation pattern, path lengths, winding, and the number/location of ccw faces. The monotone trend therefore does not establish that balance per se causes the quality improvement; the shelling order or other correlated structural changes could be doing the work. The paper never acknowledges this confound, and the heuristic's priority is based on incoming-edge counts rather than δ directly, which makes the connection between its objective and the measured metric indirect. On top of that, there are no significance tests, and the separator baseline is essentially just Fox-Epstein et al., so the state-of-the-art comparison is incomplete.\n\nBut these are addressable issues, not load-bearing flaws. The central claim—that balanced Schnyder woods are a practical preprocessing step for drawing and separating mesh-like graphs—is plausible and supported by the comparison against minimal woods, even if the isolated causal role of balance is not proven. A control experiment that perturbs balance while holding other structure fixed would strengthen the paper considerably, and the author should be asked to add one.\n\nThe paper is for researchers in graph drawing and experimental algorithms who work with planar triangulations. It deserves a serious referee, not a desk reject, and I would recommend conditional acceptance after the causal evidence is improved.","headline":"A careful, well-scoped experimental study of a new balance heuristic for Schnyder woods; the causal claim about balance itself is plausible but not isolated from confounds.","tokens_in":10273,"tokens_out":1579,"would_cite":false,"duration_ms":17266,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A balance heuristic for Schnyder woods improves planar drawings and separators","keywords":["Schnyder woods","planar triangulations","graph drawing","cycle separators","linear-time heuristic","balanced orientations","experimental algorithms","mesh regularity"],"falsifier":"Take a single near-regular triangulation with about a million vertices, run the balanced heuristic over many random seeds, and compare the worst-case separator boundary and drawing edge-length metric to a minimal Schnyder wood; if the worst balanced result is no better than the minimal one, the claim that balance drives quality is falsified.","tokens_in":9404,"feed_emoji":"📐","tokens_out":7197,"duration_ms":74013,"temperature":0.7,"pith_summary":"The paper claims that simple linear-time heuristic choices inside a standard vertex shelling can produce Schnyder woods whose three color classes are balanced at each vertex. Experiments across real-world meshes, random triangulations, and synthetic regular grids suggest these balanced woods make Schnyder drawings more regular—fewer long edges and flat triangles—and provide short, balanced cycle separators. The practical payoff is speed: the heuristic processes over a million vertices per second, and once the drawing exists, a separator is read off almost instantly. No worst-case guarantee is claimed; the contribution is empirical evidence that exploiting regularity in real inputs works.","feed_headline":"Balanced Schnyder woods improve planar drawings and separators","feed_subtitle":"Tests on real and synthetic triangulations show better layouts and short cycle separators.","key_machinery":"The load-bearing mechanism is a priority-based vertex conquest. The standard shelling maintains a boundary cycle and repeatedly removes a free vertex, assigning colors and orientations to its incident edges; the heuristic gives each boundary vertex a priority equal to the number of incoming edges already assigned to it, stores vertices in a small number of queues by priority, and always removes the highest-priority free vertex. This retards vertices with few incoming edges, so they accumulate edges of several colors before being removed, which is what keeps defects small. A post-processing reversal of oriented triangles can further raise the fraction of balanced vertices on regular graphs, at extra cost.","core_discovery":"A Schnyder wood is an edge coloring and orientation of a rooted planar triangulation in which every inner vertex has one outgoing edge of each of three colors; the paper measures its balance by a defect $\\delta(v)$, the spread between the most- and least-frequent incoming colors (with a small correction when the degree is not divisible by 3). The central discovery is that retarding the removal of vertices that have accumulated few incoming edges during the incremental shelling produces woods in which most vertices are balanced, and that this balance is strongly associated with drawing quality and separator quality. On a fixed seed, the paper generates a sequence of woods from balanced to unbalanced by randomly reversing oriented triangles, and both the edge-length layout metric and separator boundary size worsen as the average defect increases.","pith_inferences":["I infer the likely mechanism behind the empirical correlation: balanced woods spread the three color classes evenly around each vertex, preventing the long spiraling paths that both stretch edges and inflate separator boundaries; this suggests the same balancing should help other Schnyder-wood applications such as compact encodings and spanners.","A natural testable extension is to apply the priority rule to non-triangulated planar graphs (after a preprocessing triangulation) or to higher-genus maps, and check whether balance still predicts layout and separator quality.","To separate balance from other shelling effects, one could run a control that perturbates the shelling order while keeping priority structure fixed; if quality does not track the defect, the causal claim would need revision."],"forward_implications":["On regular meshes, a large majority of vertices become balanced (about 79% for a spherical grid-type graph), whereas minimal Schnyder woods leave most vertices with large defect.","Schnyder drawings obtained from balanced woods have higher edge-length uniformity and capture regular structure; unbalanced woods show long edges and flat triangles.","Cycle separators extracted from balanced woods have boundary sizes well below the $\\sqrt{8m}$ bound on most tested graphs, often close to $\\sqrt{m}$, with balanced partitions meeting the $2/3$ ratio.","Separator extraction after the drawing is computed is near-instantaneous (about 0.01 seconds for graphs with around a million vertices).","The choice of initial seed has limited effect on balance, but for high-diameter graphs it can materially change separator length."],"supporting_citations":[{"why":"Schnyder's original construction of the wood and the grid drawing; supplies the object whose balance is studied.","marker":"[27]"},{"why":"The incremental vertex shelling procedure that the heuristic modifies with priority queues.","marker":"[7]"},{"why":"The short cycle separator benchmark and the $\\sqrt{8m}$ boundary-size bound used for comparison.","marker":"[15]"},{"why":"Earlier engineered separator implementations whose running times serve as the comparison baseline.","marker":"[19]"},{"why":"Uniform random sampling of triangulations used to generate random test inputs.","marker":"[26]"},{"why":"Shows a rooted triangulation admits many realizers, the space the heuristic searches.","marker":"[1]"}],"fun_headline_variants":["Balanced Schnyder woods improve planar drawing quality","Schnyder balance linked to better layouts and separators","Experimental trial: balanced woods boost graph drawing","Balanced Schnyder woods yield shorter cycle separators","Testing balanced Schnyder woods on planar triangulations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The measured correlation between balance and quality is causal, and the tested triangulations are representative enough to generalize the in-practice claim.","fun_headline_variants_meta":{"raw":{"variants":["Balanced Schnyder woods improve planar drawing quality","Schnyder balance linked to better layouts and separators","Experimental trial: balanced woods boost graph drawing","Balanced Schnyder woods yield shorter cycle separators","Testing balanced Schnyder woods on planar triangulations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000128,"raw_usage":{"total_tokens":1054,"prompt_tokens":814,"completion_tokens":240,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":163}},"tokens_in":430,"tokens_out":240,"duration_ms":3118,"temperature":1.0,"reasoning_tokens":163,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:37:26.823323+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a single near-regular triangulation with about a million vertices, run the balanced heuristic over many random seeds, and compare the worst-case separator boundary and drawing edge-length metric to a minimal Schnyder wood; if the worst balanced result is no better than the minimal one, the claim that balance drives quality is falsified.","supporting_citations":[{"cited_title":"In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","cited_arxiv_id":null,"evidence_quote":"Schnyder's original construction of the wood and the grid drawing; supplies the object whose balance is studied."},{"cited_title":"Master’s Thesis, FB Mathematik und Informatik, Freie Universit¨ at Berlin (2000)","cited_arxiv_id":null,"evidence_quote":"The incremental vertex shelling procedure that the heuristic modifies with priority queues."},{"cited_title":"ACM Journal of Experimental Algorithmics 21(1), 2.2:1–2.2:24 (2016)","cited_arxiv_id":null,"evidence_quote":"The short cycle separator benchmark and the $\\sqrt{8m}$ boundary-size bound used for comparison."},{"cited_title":"ACM Journal of Experimental Algorithmics 14 (2009), https://doi.org/10.1145/1498698.1571635","cited_arxiv_id":null,"evidence_quote":"Earlier engineered separator implementations whose running times serve as the comparison baseline."},{"cited_title":"Al- gorithmica 46(3-4), 505–527 (2006)","cited_arxiv_id":null,"evidence_quote":"Uniform random sampling of triangulations used to generate random test inputs."},{"cited_title":"Journal of Combinatorial Theory, Series A 116(1), 55–75 (2009), https://hal","cited_arxiv_id":null,"evidence_quote":"Shows a rooted triangulation admits many realizers, the space the heuristic searches."}],"review_version":1}