{"id":"1832a072-f310-4963-847a-f4eed58b7a93","arxiv_id":"1908.08365","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Any two equivalent planar orthogonal drawings of a disconnected graph with complexity n can be morphed into each other with O(n) linear morphs while preserving planarity, orthogonality, and linear complexity of intermediate drawings.","lead":"This paper proves that two planar orthogonal drawings of the same graph, even a disconnected one, can be turned into each other with at most s+1 linear morphs, where s measures their structural difference and is at most O(n). A generalist would read it because it settles the optimal asymptotic complexity of morphing orthogonal drawings while keeping intermediate drawings simple.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Lemma 2's wire-layer shortcut is terse but appears sound, and I found no concrete failure of the O(n) spirality argument.","rationale":"The reader's weakest-assumption selection points at Lemma 3 and the shortcut argument for wire-only layers, which is exactly where I concentrated my scrutiny. I agree that this is the least formally developed part of the paper: the proof is a sketch, and the shortcut operation is described at a high level. However, unlike a definitive objection, my reading of the argument found no actual gap. The key contradiction is that replacing the boundary arc of the newly chosen shortest wire w by a path along the gate line L strictly shortens w; this does not require every other wire to be shortened. Equivalence is preserved because the shortcut occurs inside a layer with no vertices or edges and the wires cross the gates in the same order. The layer count then follows from the classification into layers containing vertices, edges, and wire-only layers. I also checked the later batching and simplification steps at a high level; they are compatible with the theorem's claim, and the reliance on the earlier paper [11] is explicit and appropriate for this sequel. The paper would benefit from a fuller formal treatment of Lemma 2, but I found no concrete counterexample or circular step. Therefore the reader's ACCEPT verdict stands, and the only recommended action is an optional verification of the shortcut step on small exhaustive instances.","tokens_in":20257,"tokens_out":20139,"duration_ms":216656,"concrete_test":"Implement the Lemma 2 greedy construction for all pairs of equivalent orthogonal drawings of disconnected graphs with up to 8 vertices, using exact integer coordinates and exhaustive homotopy-class search. For each instance, assert that (1) the produced lr-wire set has spirality at most c*n for a small constant c, and (2) every layer containing only wires admits a reconnection along L that preserves the wire-edge and wire-wire crossing orders and strictly shortens the newly inserted wire w. If all small instances pass, the remaining risk is confined to the level of formal rigor, not the mathematical claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central new claim rests on Lemma 3, which in turn depends on Lemma 2's construction of an equivalent set of lr-wires with spirality O(n). The reader flagged the shortcut argument for layers containing only wires, and that is indeed the least formal part of the paper: the appendix states that after disconnecting lr-wires at the two gates of such a layer, reconnecting along L shortens all wires and preserves equivalence, but the details are sketched rather than fully specified. I examined the two properties that could fail. First, reconnecting along L could, in principle, alter the crossing order with edges or with other wires. This does not occur because the layer contains no vertex or edge, and the wires cross the two gates in the same order; reconnecting in that order preserves the equivalence pattern. Second, the replacement might not strictly shorten every affected wire. Strict shortening is not needed for every wire: the newly inserted wire w forms part of the layer boundary, and replacing its boundary arc by a path along L strictly shortens w, contradicting its choice as shortest in its homotopy class. The other wires can be rerouted consistently without increasing length. The remaining counting argument then bounds the number of layers by O(n) using vertices, edges, and the shortestness contradiction. I could not construct a concrete counterexample, and the argument, while terse, is structurally sound. The result is not machine-checked, but the geometric case analysis is consistent with the surrounding lemmas. Thus I do not see a load-bearing flaw that would overturn the reader's ACCEPT verdict.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies morphing between two equivalent planar orthogonal drawings ΓI and ΓO of a possibly disconnected graph G, while maintaining planarity, orthogonality, and linear complexity of intermediate drawings. Building on the connected-graph result of Van Goethem and Verbeek [11], which uses O(n) linear morphs via the spirality s of ΓI relative to ΓO, the paper proves that s+1 linear morphs always suffice, even for disconnected graphs, and since s=O(n) this is asymptotically optimal. The proof proceeds in three stages: (1) constructing an equivalent set of lr- and tb-wires with spirality O(n) for disconnected graphs (Section 3, Lemmas 1-3), (2) showing that each unit of spirality reduction can be batched into a single linear morph (Section 4, Theorem 2 and Lemmas 4-9), and (3) adapting the rerouting and simplification operations of [11] so that the batched morphs maintain linear complexity of the intermediate drawings (Section 5, Theorem 3). The paper is a full version with appendix proofs, and includes an implementation video.","tokens_in":20510,"tokens_out":15476,"duration_ms":148566,"significance":"If correct, this result settles the optimal linear bound for morphing planar orthogonal drawings of disconnected graphs, improving the previous O(n^1.5) bound for the disconnected case and matching the Ω(n) lower bound of Alamdari et al. for straight-line morphs. The main technical novelties are the wire-construction lemma for disconnected graphs (Lemma 3), which handles multiple homotopy classes per wire, and the batching argument (Section 4) that compresses an entire spirality unit into one linear morph. The paper is parameter-free in the sense that the construction uses no fitted constants, the lower bound is cited from external work, and the central proof chain from wires to batching to complexity control is internally consistent. The main text is explicit that several arguments are sketches, with fuller (though in places still terse) versions in the appendix.","major_comments":[],"minor_comments":[{"comment":"The proof of Lemma 9 in the appendix gives a detailed argument only for the case where p and q both lie on vertical segments; the two remaining cases (p on a horizontal and q on a vertical segment, and both on horizontal segments) are only set up and dismissed as analogous. Since the contradiction in the first case relies on vertical segments pr and qs, the analogous arguments for the other cases are not immediate and should be spelled out.","section":"Appendix, Lemma 9"},{"comment":"The shortcut argument in the proof of Lemma 2 is the least formal step of the wire construction: the sentence 'Disconnect all lr-wires at the gates of R... All wires crossing R have been shortened by this' asserts both that the reconnection preserves the equivalence pattern and that every affected wire is strictly shortened. Please expand this step to justify explicitly that reconnecting along L cannot change the crossing order with edges or wires and that the replacement strictly shortens w and all other affected wires.","section":"Appendix, Lemma 2"},{"comment":"The statement 'As a corollary of Lemma 4, any slides along links of the wires outside of the ε-band do not affect the k-windmill next to e' is not immediate, because Lemma 4 concerns inversions of vertices, not the geometry of windmills. The connection should be explained.","section":"Section 5.1, Lemma 10"},{"comment":"The proof of Lemma 3 invokes 'Lemma 2 from [11]' for the fact that intersecting links have the same spirality. Since this fact is load-bearing for the transfer from lr-wires to tb-wires, please state the lemma explicitly or give the precise reference.","section":"Section 3, Lemma 3"},{"comment":"The notation Γi−−▶Γj and Γi =▶Γj is unusual and slightly hard to parse; consider defining it more prominently or using a more standard arrow notation.","section":"Section 2, Notation"}],"recommendation":"minor_revision","confidential_remarks":"The paper is strong and the central proof chain is sound. The only reason I am not recommending acceptance as is that a few appendix proofs (notably Lemma 9 and Lemma 2) are more sketchy than 'full proofs' would warrant and would benefit from expansion; these are local fixes that do not affect the validity of the results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper finishes the job the authors started in their SoCG 2018 paper: it brings disconnected planar orthogonal drawings down to O(n) linear morphs, matching the straight-line lower bound. The new exportable piece is the s+1 bound and, more importantly, the wire-construction lemma (Lemma 3) that keeps spirality O(n) even when connectivity is absent. That is a real advance, not just a tweak: the earlier connectivity augmentation route gave O(n^1.5), and the homotopy-class ambiguity for disconnected graphs is a genuine obstruction they had to engineer around.\n\nWhat the paper does well: the batching argument (Theorem 2) and the rerouting/simplification lemmas are substantial, and the appendix gives real proofs rather than hand-waving. I followed the central chain from Lemma 3 to Theorem 3 and did not find a load-bearing gap. I also checked the stress-test note on Lemma 2's shortcut argument, which is the least formal step. It holds: the layer-boundary wire is strictly shortened, contradicting its choice as shortest, and the rerouting preserves the crossing order because the layer contains no vertices or edges. The terse part is the reconnection order at the gates; the appendix sketches it, and I believe it is sound, but this is where I would want a referee to spend time.\n\nSoft spots, in proportion. First, the paper is not self-contained: it repeatedly invokes Theorem 8 and Lemma 9 from [11] as black boxes, so the reader must have that paper open. That is normal for a sequel, but worth stating. Second, the \"optimal\" in the title means asymptotically optimal in n; the s+1 bound itself is not shown tight, and the lower bound is inherited from the straight-line case rather than for the orthogonal-disconnected setting. Not a flaw, just calibration. Third, some proof sketches in the main text (Lemma 5, Lemma 9) are quite compressed, though the appendix expands them reasonably.\n\nWho this is for: anyone working in graph drawing, especially orthogonal morphing and spirality. It is a meaningful closing of an asymptotic gap, not a reshaping of the field. The citation pattern is honest: the heavy self-citation is legitimate because the prior framework is being refined, and the new claims are proved from wire combinatorics rather than assumed.\n\nI would send this to a serious referee. My own verdict is accept; I would ask the referee to check Lemma 2 and the rerouting invariance in Lemma 10 carefully, but I do not expect those to break.","headline":"A solid, genuinely new result that closes the disconnected orthogonal morphing problem at the asymptotically optimal O(n) bound, though it leans heavily on the authors' prior framework.","tokens_in":21080,"tokens_out":1976,"would_cite":true,"duration_ms":23141,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that equivalent planar orthogonal drawings of a disconnected graph morph into each other with at most $s+1$ linear morphs, where $s$ is the spirality of the starting drawing and $s = O(n)$.","keywords":["planar orthogonal drawings","morphing","wires","spirality","disconnected graphs","linear morphs","graph drawing","planarity"],"falsifier":"A concrete disproof would be an explicit pair of equivalent planar orthogonal drawings of a disconnected graph with $n$ vertices for which every equivalent set of wires has spirality growing faster than linearly in $n$; such an example would refute the $O(n)$ morph theorem immediately. A narrower test is to search for a single wire whose spiral contains a layer empty of both vertices and edges but full of previously selected shortest wires; if shortcutting that layer yields a wire that is not equivalent to $\\Gamma_O$, then the proof of Lemma 3 fails at that point.","tokens_in":20047,"feed_emoji":"📐","tokens_out":10286,"duration_ms":90826,"temperature":0.7,"pith_summary":"Two planar orthogonal drawings of the same graph can be reshaped into each other by a sequence of simple linear interpolations without ever losing planarity, orthogonality, or reasonable drawing complexity. This paper proves that the number of such linear morphs is at most $s+1$, where $s$ is the spirality of the starting drawing relative to the target; since a suitable wire set always has $s = O(n)$, the bound is $O(n)$ even when the graph is disconnected. Earlier methods needed $O(n^{1.5})$ morphs in the disconnected case, so this matches the lower bound that was already known for straight-line drawings. The proof works by picking separator curves (wires) of low spirality, then compressing each unit drop of spirality into one linear morph, with a rerouting and redrawing step that keeps intermediate complexity linear at the cost of one extra morph.","feed_headline":"Disconnected orthogonal drawings morph in O(n) linear morphs","feed_subtitle":"A new wire-selection lemma keeps spirality linear, matching the straight-line lower bound and preserving planarity throughout.","key_machinery":"The central object is a wire, an orthogonal polyline that separates the drawing into left/right or top/bottom parts and records the order in which vertices, edges, and other wires are crossed; a set of matched left-to-right and top-to-bottom wires encodes the structural difference between the two drawings. Spirality of a wire is the maximum absolute number of left turns minus right turns accumulated along any of its links, and it serves as the distance measure being driven down to zero. The argument is carried by three mechanisms: shortest-compatible wire insertion, which pins spirality to $O(n)$; staircases, which are chains of maximum-spirality links that isolate the pairs of vertices whose order changes, enabling each unit of spirality to be removed by one linear morph; and windmill rerouting with redraw steps, which keep the number of bends added per iteration linear so the final drawing has linear complexity.","core_discovery":"The central claim is that two equivalent planar orthogonal drawings $\\Gamma_I$ and $\\Gamma_O$ of a possibly disconnected graph $G$ admit a morph into each other using $s+1$ linear morphs, where $s$ is the spirality of $\\Gamma_I$ relative to $\\Gamma_O$, and every intermediate drawing stays planar, orthogonal, and of linear complexity. Because Lemma 3 guarantees an equivalent set of wires with spirality $O(n)$, this gives an optimal $O(n)$ bound, matching the straight-line lower bound. The construction is connectivity-agnostic: the graph may fall into any number of components, and the wire set still has linear spirality because each wire is chosen as the shortest one compatible with its predecessors, so any overly spiral layer must contain a vertex or an edge and there can be only $O(n)$ such layers. The remaining work shows that all intermediate morphs that reduce spirality by one can be executed together in a single linear morph, and that rerouting and simplification can be adapted to this batching so intermediate complexity never grows beyond linear.","pith_inferences":["If the shortest-wire argument is as robust as it appears, the same selection principle might yield low-complexity morphs for other equivalence notions—for example, orthogonal drawings with prescribed edge routes or drawings on surfaces—where separators can be described by homotopy classes rather than straight lines.","The paper leaves open whether the final morph count can be lowered from $s+1$ to exactly $s$ while still keeping all intermediate drawings of linear complexity; the tradeoff between one extra morph and quadratic-or-worse intermediate complexity is an artifact of the construction, not a proven barrier.","The windmill-rerouting technique, which bundles all wires crossing an edge into a spiral structure, may be independently useful for reducing bend complexity in other orthogonal drawing algorithms that update drawings locally."],"forward_implications":["The $O(n)$ upper bound now holds for all planar orthogonal drawings, connected or not, and therefore matches the straight-line lower bound of $\\Omega(n)$, so the worst-case number of linear morphs is optimal.","Without the rerouting-and-simplification refinement, exactly $s$ linear morphs suffice while preserving planarity and orthogonality, at the cost of $O(n^3)$ intermediate complexity; with the refinement, $s+1$ morphs keep intermediate complexity linear.","The wire construction and batching arguments do not depend on the graph being connected, so the same algorithm covers arbitrary numbers of components without any preprocessing that inflates the drawing.","Every intermediate drawing during the morph is planar, orthogonal, and of linear complexity, which means the morph can be used in interactive settings where the mental map of the drawing must be preserved.","Because spirality can be computed and the morph sequence is explicit, the result yields a constructive algorithm that runs from any two equivalent orthogonal drawings to a sequence of linear morphs."],"supporting_citations":[{"why":"The previous O(n)-morph algorithm for connected graphs whose spirality and wire machinery this paper refines and reuses.","marker":"[11]"},{"why":"Establishes the O(n) lower bound for straight-line planar morphs, which this paper's O(n) bound matches.","marker":"[1]"},{"why":"Compatible connectivity augmentation for disconnected graphs, the O(n^{1.5}) barrier this paper removes.","marker":"[2]"},{"why":"Earlier O(n^2)-morph algorithm for orthogonal drawings that introduced slides, the linear-morph primitive used here.","marker":"[4]"},{"why":"Introduces spirality, the measure of structural distance that the whole argument drives to zero.","marker":"[8]"}],"fun_headline_variants":["Optimal O(n) morphs for disconnected orthogonal drawings","Linear morphs now possible for disconnected orthogonal drawings","Matching lower bound: O(n) morphs for disconnected graphs","Wire-selection lemma yields optimal morphing complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction hangs on Lemma 3's claim that one can always choose an equivalent set of wires whose spirality is linear in the size of the drawing; that claim relies on being able to shortcut any spiral layer that contains no vertex or edge, because a layer containing only other wires would mean the chosen wire was not already the shortest compatible one. If shortcutting an empty layer ever produces a wire that is no longer equivalent to the target drawing, the linear spirality bound, and the $O(n)$ morph bound along with it, breaks.","fun_headline_variants_meta":{"raw":{"variants":["Optimal O(n) morphs for disconnected orthogonal drawings","Linear morphs now possible for disconnected orthogonal drawings","Matching lower bound: O(n) morphs for disconnected graphs","Wire-selection lemma yields optimal morphing complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000369,"raw_usage":{"total_tokens":2020,"prompt_tokens":1029,"completion_tokens":991,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":926}},"tokens_in":645,"tokens_out":991,"duration_ms":9080,"temperature":1.0,"reasoning_tokens":926,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:40:49.479465+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete disproof would be an explicit pair of equivalent planar orthogonal drawings of a disconnected graph with $n$ vertices for which every equivalent set of wires has spirality growing faster than linearly in $n$; such an example would refute the $O(n)$ morph theorem immediately. A narrower test is to search for a single wire whose spiral contains a layer empty of both vertices and edges but full of previously selected shortest wires; if shortcutting that layer yields a wire that is not equivalent to $\\Gamma_O$, then the proof of Lemma 3 fails at that point.","supporting_citations":[{"cited_title":"Optimal morphs of planar orthogonal drawings","cited_arxiv_id":null,"evidence_quote":"The previous O(n)-morph algorithm for connected graphs whose spirality and wire machinery this paper refines and reuses."},{"cited_title":"How to morph planar graph drawings.SIAM Journal on Computing , 46(2):824–852, 2017","cited_arxiv_id":null,"evidence_quote":"Establishes the O(n) lower bound for straight-line planar morphs, which this paper's O(n) bound matches."},{"cited_title":"Compatible connectivity augmentation of planar disconnected graphs.Discrete & Computational Geometry, 54(2):459–480, 2015","cited_arxiv_id":null,"evidence_quote":"Compatible connectivity augmentation for disconnected graphs, the O(n^{1.5}) barrier this paper removes."},{"cited_title":"Morphing orthog- onal planar graph drawings.ACM Transactions on Algorithms , 9(4):29:1–29:24, 2013","cited_arxiv_id":null,"evidence_quote":"Earlier O(n^2)-morph algorithm for orthogonal drawings that introduced slides, the linear-morph primitive used here."},{"cited_title":"Spirality and optimal orthogonal drawings","cited_arxiv_id":null,"evidence_quote":"Introduces spirality, the measure of structural distance that the whole argument drives to zero."}],"review_version":1}