{"id":"276be1f9-8f3f-4ee5-b3f8-9c492a04a0fe","arxiv_id":"1908.05015","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"OrthogonalPlanarity is decidable in polynomial time for bounded-treewidth planar graphs, and in O(n^3 log n) time for series-parallel graphs.","lead":"The paper gives a fast algorithm for deciding whether a planar graph with bounded treewidth can be drawn orthogonally with few bends. It introduces a compressed data structure that lets the dynamic program store whole families of drawings instead of individual ones.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4, the join-step correctness lemma, is stated without proof; the sufficiency of the join-phase checks is the load-bearing unverified condition for Theorem 1.","rationale":"The reader's weakest_assumption identifies exactly the join-step correctness lemma (Lemma 4), which is stated without proof. My review confirms this is the most load-bearing concern: all other lemmas (1, 2, 3, 5) are either proved or given proof sketches in the appendix, but Lemma 4 has no proof or even a proof sketch. The join operation is the heart of the dynamic program, and its sufficiency is not obvious: sketched embeddings discard internal vertices and faces, and the algorithm relies on an arbitrary connected sketched embedding, so it is conceivable that the local checks pass while no actual orthogonal drawing exists. This does not demonstrate an internal inconsistency, but it leaves the central claim (Theorem 1 and Corollary 1) unverified. The appropriate disposition is therefore a conditional one, pending a complete correctness argument for Lemma 4. I agree with the reader's assessment and see no need to change the verdict.","tokens_in":17701,"tokens_out":11626,"duration_ms":125029,"concrete_test":"Provide a complete proof of the sufficiency direction of Lemma 4 for the join node: from the success of phase 1 (planar embedding of the union, orientation consistency) and phase 2 (shape restrictions to child sketches and bend budget), construct an orthogonal representation of G_i satisfying Definition 1. In particular, show that the resulting face boundaries and angle sums are consistent, and that the choice of connected sketched embedding does not affect the outcome. If the proof requires an additional condition not checked by the algorithm, the lemma is false as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4's algorithm OrthoPlanTester is correct only if Lemma 4 holds, but Lemma 4 is asserted with no proof (the appendix supplies only the runtime Lemma 5). The join node is the only step that combines two partial solutions; its phase 1 checks that the union of two connected sketched embeddings has a planar embedding compatible with each child, and phase 2 checks that a generated shape restricts to child sketches and that the bend budget holds. Whether these local conditions are sufficient for the existence of a genuine orthogonal representation of the union graph is non-obvious, because sketched embeddings abstract away forgotten vertices and internal face structure, and the algorithm uses an arbitrary connected sketched embedding whose choice can affect planarity of the union. A false-positive here would make the algorithm accept a graph with no valid drawing, breaking Theorem 1 and Corollary 1. This is precisely the unproved load-bearing step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the notion of an orthogonal sketch, an equivalence class of orthogonal representations of a graph with respect to an active vertex set, and uses it in a bottom-up dynamic program over a nice tree-decomposition to decide OrthogonalPlanarity. The main algorithmic claim (Theorem 1) is an f(k,σ,b)·n-time decision procedure for n-vertex planar graphs of maximum degree four, where k is the treewidth, σ is the number of degree-2 vertices, and b is the bend budget; Corollary 1 derives k^{O(k)} n^{k+1} log n time when parameterized by treewidth alone. The paper further claims extensions to HV-Planarity and FlexDraw, including an O(n^3 log n) algorithm for series-parallel graphs. The central correctness statement is Lemma 4, which asserts that the dynamic program accepts exactly the graphs admitting an orthogonal drawing with at most b bends.","tokens_in":17854,"tokens_out":14349,"duration_ms":153939,"significance":"If the results are correct, they place OrthogonalPlanarity in XP for bounded treewidth, improve the best known bound for series-parallel graphs from O(n^4) to O(n^3 log n), and provide a uniform framework covering HV-Planarity and FlexDraw. The orthogonal sketch abstraction is natural, and the counting arguments in Lemmas 1–3 are detailed and largely plausible. However, the load-bearing correctness lemma for the join operation (Lemma 4) is stated without proof, and the bend-accounting in the dynamic program conflates a signed roll-up number with a bend count. These gaps must be resolved before the main claims are established.","major_comments":[{"comment":"Lemma 4 is the if-and-only-if correctness statement for the whole algorithm, but it is asserted without proof; the appendix supplies only the missing part of the runtime proof of Lemma 5. The join phase combines local checks — planarity of the union of connected sketched embeddings compatible with the child embeddings, face-orientation consistency, existence of restricting shapes in Bj and Bj′, and the bend budget — but no argument shows that these local conditions are sufficient to guarantee an orthogonal representation of Gi satisfying Definition 1, nor that every valid representation of Gi yields sketches that pass the checks. Since Theorem 1 and Corollary 1 rest entirely on Lemma 4, this is a load-bearing gap that must be closed with a full proof, including the cases of disconnected graphs and vertices appearing multiple times on a face boundary.","section":"Section 4, join node (ending 'We conclude: Lemma 4')"},{"comment":"The algorithm computes 'a' connected sketched embedding for each child sketch, but Section 3 states that different connected sketched embeddings of the same sketched embedding may exist, and the subsequent planarity test of the union C depends on the dummy vertices and edges added. An arbitrary choice could reject a valid merge or accept an invalid one. The assertion that 'any connected sketched embedding encodes the information about the global structure of H that is sufficient' is not proved. The algorithm must either enumerate all relevant choices or prove an invariance lemma showing that the choice does not affect the ability to detect a valid glued representation.","section":"Section 3 and Section 4, join phase 1"},{"comment":"The text says 'ρ(v,ui) corresponds to the number of bends along the edge (v,ui)' and later uses '|ρ(u,v)|' as the number of bends along shared edges in Ei. By the definition in Section 3, ρ is a signed net turn (n_{π/2} − n_{3π/2} − 2n_{2π}), not a bend count. A single edge with one 90° and one 270° bend has ρ = 0 on each dart but contains two bends, so |ρ| undercounts the bend count unless an unstated normalization to bend-minimal representatives is assumed. Since the bend budget is central to the decision procedure, the paper must either prove that in a bend-minimal representation within a shape class every edge path has all bends in the same direction, or maintain additional information to compute the true accumulated bend count; the introduce-phase inequality should also use absolute values (or the correct formula) if negative roll-up numbers are permitted.","section":"Section 4, introduce-vertex and join bend checks"}],"minor_comments":[{"comment":"There is a missing space in 'algorithmOrthoPlanTester' that should read 'algorithm OrthoPlanTester'.","section":"Appendix B, Lemma 5 missing part"},{"comment":"The phrase '2n′2π(f)' appears to be a typo; it should presumably read 'n′2π(f)'.","section":"Appendix A, Lemma 3 proof"},{"comment":"The condition 'If v is the only vertex of Cf' is ambiguous when v occurs multiple times on the closed walk of a representing cycle; please clarify that it means v is the only distinct vertex on the cycle, or describe how to handle each occurrence separately.","section":"Section 4, forget-vertex case"},{"comment":"The symbol b* is used both as the maximum edge weight in FlexDraw and in the runtime bound; consider defining it in the theorem statement for readability.","section":"Section 5, Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"The missing proof of Lemma 4 is the primary obstacle to accepting the paper. The bend-count/roll-up issue is not merely expository: the algorithm's budget checks are stated in terms of a quantity that is not the number of bends in general, so the correction may require more than a proof detail. I still recommend major revision rather than rejection because the gaps are potentially fixable within the manuscript's scope, and the main ideas are interesting and likely significant if the gaps are closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: a genuinely useful FPT/XP result for OrthogonalPlanarity on bounded-treewidth graphs, with a concrete improvement for series-parallel graphs, but the paper as written has a load-bearing proof gap at the join step.\n\nWhat's new: the orthogonal sketch abstraction is a natural and clever way to compress the relevant set of orthogonal representations into finitely many equivalence classes. It yields the first polynomial-time algorithm for fixed treewidth (Corollary 1) and O(n^3 log n) time for series-parallel graphs, beating the old O(n^4) bound. The extensions to HV-Planarity and FlexDraw are plausible and follow from the same machinery. Lemmas 1–3 in the appendix are argued in detail, and the counting bounds look right.\n\nThe soft spot, and it is not minor: Lemma 4, which states the algorithm is correct, is asserted without proof. Section 4 ends the join-node description with 'We conclude: Lemma 4.' There is no argument anywhere in the paper. The join phase checks that two sketched embeddings, after adding dummy vertices, admit a common planar embedding compatible with the children, and that shapes exist whose restrictions match the child sketches and whose bend counts fit the budget. What is not shown is that these local conditions are sufficient for the existence of an actual orthogonal representation of the union graph. Sketched embeddings discard forgotten vertices and internal face structure, so the checks may miss global constraints. If Lemma 4 is false, the algorithm could accept graphs that have no valid orthogonal drawing, invalidating Theorem 1 and Corollary 1. Lemma 5, the runtime bound, is also a sketch, but it's the kind of thing that can be checked line by line; the missing correctness proof is the real issue.\n\nThis is not a takedown: the core idea has legs, and the missing lemma might be provable. The counting lemmas suggest the authors worked through substantial detail. But as submitted, the main theorem is not backed by a complete correctness argument. A careful referee should ask for a full proof of Lemma 4, ideally with a more detailed join-phase argument.\n\nWho this is for: people working on parameterized complexity of graph drawing, especially orthogonal representations and treewidth. They should read it, with the caveat above.\n\nRecommendation: send it to peer review, with the expectation that the authors supply a complete proof of Lemma 4. A desk reject would be wrong; the result is important enough to give them the chance.\n\nBest.","headline":"Strong FPT/XP result for bounded-treewidth OrthogonalPlanarity with a real series-parallel improvement, but the central correctness lemma is asserted without proof.","tokens_in":18383,"tokens_out":2425,"would_cite":false,"duration_ms":24083,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R10","05C85","68Q25","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Fixed treewidth makes orthogonal planarity polynomial","keywords":["orthogonal planarity","treewidth","fixed-parameter tractable algorithms","orthogonal sketches","bend minimization","HV-planarity","series-parallel graphs","FlexDraw"],"falsifier":"Run OrthoPlanTester and a brute-force enumeration of all orthogonal representations with at most $b$ bends on the same small series-parallel graphs, up to about ten vertices, focusing on graphs built by joining two components along a shared set of boundary vertices. A graph where the algorithm answers yes but no drawing exists would disprove the merge step; the natural place to look is a pair of shape-compatible sketches whose merged angle assignment violates the face balance law or forces a vertex angle sum greater than $2\\pi$, since those are the only conditions the merge checks.","tokens_in":17515,"feed_emoji":"📐","tokens_out":10115,"duration_ms":89876,"temperature":0.7,"pith_summary":"OrthogonalPlanarity asks whether a planar graph can be drawn with axis-parallel edges and at most $b$ bends in total; it is NP-complete even when $b=0$. This paper claims that bounded treewidth removes the hardness: it gives an algorithm that decides the problem in $f(k,\\sigma,b)\\cdot n$ time, where $k$ is the treewidth, $\\sigma$ the number of degree-2 vertices, and $b$ the bend budget. The method replaces full drawings by orthogonal sketches, one per bag of a tree-decomposition, so that only the shape of a drawing on the bag's active vertices is remembered. If the algorithm's merge step is correct, OrthogonalPlanarity is polynomial for every fixed treewidth, runs in $O(n^3\\log n)$ for series-parallel graphs, and the same sketches decide HV-Planarity and FlexDraw on bounded-treewidth inputs.","feed_headline":"Fixed treewidth makes orthogonal planarity polynomial","feed_subtitle":"Sketch-based FPT algorithm runs in k^O(k)(b+σ)^k · n time; series-parallel decision drops to O(n^3 log n).","key_machinery":"An orthogonal sketch is a sketched embedding together with a shape. The sketched embedding keeps only the representing cycles of faces that contain active vertices: oriented cycles through the active vertices in their boundary order. The shape assigns to each dart of the sketch a vertex-angle value $\\varphi$ and a roll-up number $\\rho$, an integer that records how the face winds between consecutive active vertices by counting right turns against left turns along the corresponding boundary path. Lemma 2 is the balance law every cycle must satisfy, and Lemma 3 bounds the number of distinct sketches by $w^{O(w)}(\\sigma+b)^{w-1}$ for a bag of size $w$, because only $w-1$ roll-up numbers can be chosen freely once vertex angles are fixed. This state-space bound is what keeps the dynamic program's per-bag work within $k^{O(k)}(\\sigma+b)^k\\log(\\sigma+b)$.","core_discovery":"The central discovery is a dynamic program over a nice tree-decomposition whose states are shape-equivalence classes of orthogonal representations, called orthogonal sketches. Two representations are equivalent when they have the same sketched embedding on the active vertices and the same shape functions $\\varphi$ and $\\rho$; the paper bounds the number of such classes by $k^{O(k)}(\\sigma+b)^{k-1}$. Theorem 1 states that OrthogonalPlanarity with budget $b$ is decidable in $k^{O(k)}(\\sigma+b)^k \\log(\\sigma+b)\\cdot n$ time given a width-$k$ decomposition. Corollary 1 then observes that both $\\sigma$ and $b$ are $O(n)$, so the problem is decidable in $k^{O(k)}n^{k+1}\\log n$ time and a bend-minimum drawing can be found in $k^{O(k)}n^{k+1}\\log^2 n$ time. For treewidth 2 this gives $O(n^3\\log n)$ decision and $O(n^3\\log^2 n)$ bend minimization, without the biconnectivity restriction of the previous $O(n^4)$ series-parallel algorithm, and the same machinery gives $O(n^3\\log n)$ HV-Planarity for series-parallel graphs.","pith_inferences":["If the missing proof of Lemma 4 is supplied, the sketch framework should transfer to other drawing conventions whose validity is a conjunction of local vertex and face conditions, such as octilinear drawings or drawings with prescribed edge directions; the paper does not pursue this.","The explicit dependence on the number $\\sigma$ of degree-2 vertices suggests that long chains of degree-2 vertices are what make the state space grow; contracting maximal degree-2 paths and remembering only their lengths might reduce the bound, but the paper does not claim this.","Because the merge step is unproved in this version, the series-parallel speedups should be read as conditional on that lemma; finding a counterexample would not kill the sketch idea but would force a stronger compatibility test at join nodes.","The XP bound $k^{O(k)}n^{k+1}\\log n$ leaves open whether OrthogonalPlanarity is FPT when parameterized by treewidth and bend budget alone; the authors explicitly raise this as an open problem."],"forward_implications":["For every fixed treewidth $k$, OrthogonalPlanarity is decidable in polynomial time, placing the problem in XP when parameterized by treewidth.","Series-parallel graphs, which have treewidth 2, get $O(n^3\\log n)$ decision and $O(n^3\\log^2 n)$ bend minimization, improving the previous $O(n^4)$ bound and dropping its biconnectivity restriction.","HV-Planarity is decidable in $O(n^3\\log n)$ for series-parallel graphs, improving the previous $O(n^4)$ algorithm for that class.","FlexDraw is solvable in polynomial time for bounded-treewidth graphs by subdividing each edge $\\psi(e)$ times and then testing a bendless drawing.","The algorithm is constructive: on a positive answer it outputs an orthogonal drawing, and a binary search on the budget $b$ yields a bend-minimum drawing."],"supporting_citations":[{"why":"supplies the orthogonal representation characterization and the linear-time conversion from a representation to a drawing that the whole approach is built on.","marker":"[29]"},{"why":"proves OrthogonalPlanarity NP-complete for b=0, the hardness result that motivates the parameterized algorithm.","marker":"[24]"},{"why":"gives the linear-time tree-decomposition algorithm that provides the width-k decomposition assumed by Theorem 1.","marker":"[7]"},{"why":"defines nice tree-decompositions, the traversal structure the dynamic program uses.","marker":"[26]"},{"why":"is the previous O(n^4) series-parallel algorithm restricted to biconnected graphs and the source of the spirality concept that the roll-up number generalizes.","marker":"[13]"},{"why":"provides the earlier parameterized algorithm for variable-embedding orthogonal drawings whose degree-4 parameterization is extended here.","marker":"[15]"},{"why":"gives the O(n^4) HV-Planarity algorithm for series-parallel graphs that Corollary 2 improves.","marker":"[17]"},{"why":"defines the FlexDraw problem with flexibility constraints that Theorem 3 extends to bounded treewidth.","marker":"[5]"}],"fun_headline_variants":["Treewidth unlocks polynomial-time orthogonal planarity","Series-parallel orthogonal planarity now O(n^3 log n)","Sketch-based DP speeds orthogonal planarity on bounded treewidth","Orthogonal planarity solvable in cubic time for series-parallel"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the join step: the algorithm assumes that any two partial drawings encoded by sketches that agree on the shared boundary vertices and whose combined bend count fits the budget can always be merged into a valid drawing of the whole graph. This step is asserted in Lemma 4 without proof.","fun_headline_variants_meta":{"raw":{"variants":["Treewidth unlocks polynomial-time orthogonal planarity","Series-parallel orthogonal planarity now O(n^3 log n)","Sketch-based DP speeds orthogonal planarity on bounded treewidth","Orthogonal planarity solvable in cubic time for series-parallel"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000291,"raw_usage":{"total_tokens":1716,"prompt_tokens":978,"completion_tokens":738,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":669}},"tokens_in":594,"tokens_out":738,"duration_ms":7588,"temperature":1.0,"reasoning_tokens":669,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:25:19.033305+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OrthoPlanTester and a brute-force enumeration of all orthogonal representations with at most $b$ bends on the same small series-parallel graphs, up to about ten vertices, focusing on graphs built by joining two components along a shared set of boundary vertices. A graph where the algorithm answers yes but no drawing exists would disprove the merge step; the natural place to look is a pair of shape-compatible sketches whose merged angle assignment violates the face balance law or forces a vertex angle sum greater than $2\\pi$, since those are the only conditions the merge checks.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the orthogonal representation characterization and the linear-time conversion from a representation to a drawing that the whole approach is built on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves OrthogonalPlanarity NP-complete for b=0, the hardness result that motivates the parameterized algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the linear-time tree-decomposition algorithm that provides the width-k decomposition assumed by Theorem 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines nice tree-decompositions, the traversal structure the dynamic program uses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"is the previous O(n^4) series-parallel algorithm restricted to biconnected graphs and the source of the spirality concept that the roll-up number generalizes."},{"cited_title":"In: ISAAC 1998","cited_arxiv_id":null,"evidence_quote":"provides the earlier parameterized algorithm for variable-embedding orthogonal drawings whose degree-4 parameterization is extended here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the O(n^4) HV-Planarity algorithm for series-parallel graphs that Corollary 2 improves."},{"cited_title":"Algorithmica 68(4), 859–885 (2014)","cited_arxiv_id":null,"evidence_quote":"defines the FlexDraw problem with flexibility constraints that Theorem 3 extends to bounded treewidth."}],"review_version":1}