{"id":"2c7bab98-0528-4807-90fb-af44755b0caf","arxiv_id":"2508.19802","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"With fixed character orderings, linear and quadratic wiggle height minimization are polynomial-time via LP/QP, while wiggle count minimization is NP-complete; a new curve-routing method and railway use case are also presented.","lead":"This paper proves that minimizing the number of wiggles in a storyline diagram is computationally hard, while giving polynomial-time optimization for minimizing total and squared vertical movement. A generalist should read it for the crisp separation of easy and hard quality criteria in a popular diagram type.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 10's rigidity assertion is load-bearing and unproved: the NP-hardness reduction collapses if frame characters can move under budget k, and 'one can convince oneself by blowing up' is not a proof.","rationale":"The central claim of the paper is the NP-completeness of WCMin (Theorem 5), and that theorem rests entirely on the reduction in Section 4.2, specifically on Lemma 10. The backward direction of Lemma 10 requires that the rigid frame is absolutely fixed in any coordination with at most k wiggles. The manuscript itself flags this as unproved: the proof says the technicalities are tedious and that one can 'convince oneself' by blowing up the construction. That is not a proof, and the assertion is not obviously true: a global translation of an entire frame component or a small local deformation could potentially preserve all relative orderings and meeting constraints while changing which wire characters count as satisfying, without adding a single wiggle. If such a coordination exists, the reduction's budget k would not enforce the intended variable assignment, and the PM3-Sat equivalence would fail. The same pattern appears in Lemmas 8 and 9, which are justified mainly by reference to figures; but the frame rigidity is the most load-bearing because it is the global assumption that makes the gadget arguments usable. I am not claiming the theorem is false—the reduction may well be repairable with a careful proof or a larger gadget. But as written, the NP-hardness result is not fully verified. The LP, QP, ILP formulations, the polynomial cases, and the experimental comparison appear solid and are supported by released code, so the paper's other contributions are not affected. Because the reader's conditional verdict already targets exactly this gap, no verdict change is needed; the condition is that Lemma 10 must be completed or machine-checked before Theorem 5 can be accepted as proven.","tokens_in":26407,"tokens_out":4838,"duration_ms":59010,"concrete_test":"For the smallest PM3-Sat instance in Figure 3, build the full ordered storyline instance (frame included) and solve the WCMin ILP of Section 4.3 under k = kcr + 5|Γ| with an additional constraint that a designated positive clause has no satisfying wire. If the solver finds a feasible coordination with at most k wiggles, Lemma 10's rigidity assertion is refuted; if infeasible, the test corroborates the lemma, leaving only the missing proof as the residual gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decision version of WCMin (Theorem 5) is proven only via Lemma 10, which asserts that ISAT is a yes-instance of PM3-Sat iff ISL has a coordination with at most k = kcr + 5|Γ| wiggles. The backward direction requires that the frame is 'completely rigid'—no frame character wiggles and the gadgets stay pinned to their intended x-coordinates. The proof in Section 4.2 states explicitly: 'the technicalities are tedious to show, but one can convince oneself by blowing up the construction,' and later 'Again, the technicalities are tedious to show...' No actual argument is supplied to show that blowing up meeting sizes prevents a coordinated shift of a frame component, or that any deviation from the intended gadget states costs an extra wiggle. The reduction is defined only graphically ('we define the storyline instance graphically'), and Lemmas 8 and 9 are likewise justified mainly by reference to Figure 5. Since k is exactly kcr + 5|Γ|, even one wiggle-saving deviation by the frame or a non-satisfying clause gadget would break the equivalence. This is a missing proof of the central claim, not a disagreement with consensus; the LP/QP results and experiments are not affected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies three wiggle-related optimization objectives for ordered storyline instances in which the vertical ordering of active characters is fixed at each time step and meetings must be drawn with prescribed spacing. The main contributions are: (i) polynomial-time LP and QP formulations for linear and quadratic wiggle height minimization, with an integrality argument for the LP; (ii) an NP-completeness result for wiggle count minimization (WCMin), based on a gadget reduction from Planar Monotone 3-Sat, together with an ILP formulation and a polynomial-time algorithm for the special case of two time steps; and (iii) a novel geometric routing method for rendering character curves with nearly parallel concentric arcs, evaluated on benchmark storyline instances and on a new rolling-stock scheduling use case. The paper is clearly written, the LP/QP and routing sections are self-contained, and the experimental section is honest about solver limitations. However, the central NP-hardness proof is incomplete as written: Lemma 10, which is the bridge between the constructed storyline instance and satisfiability of the 3-Sat formula, relies on an unproved assertion that the rigid frame is completely rigid, and the supporting Lemmas 8 and 9 are justified mainly by reference to a figure. The exactness of the ILP in Section 4.3 is also not fully established because the claimed coordinate bound is not proved.","tokens_in":26759,"tokens_out":13686,"duration_ms":168957,"significance":"If the NP-hardness proof can be completed, the paper would establish a clean complexity dichotomy: WCMin is NP-complete while linear and quadratic wiggle height minimization are polynomial-time solvable, which is a useful contribution to storyline visualization research. The LP/QP formulations, the integrality result of Proposition 1, and the experimental comparison across three objectives are valuable and appear sound. The new routing method for parallel wiggles and the rolling-stock case study are interesting and broaden the applicability of storyline techniques. The authors also ship source code, which is a concrete strength. Nevertheless, the load-bearing gap in Lemma 10 means that Theorem 5 is not proved as written, and this is the central claim of the paper. The issue is a missing proof rather than a disagreement with existing consensus, and it is fixable, but it currently blocks acceptance.","major_comments":[{"comment":"The backward direction of the NP-hardness reduction relies entirely on the claim that in any coordination with at most k = kcr + 5|Γ| wiggles, the frame is perfectly rigid, so no frame character wiggles and all gadgets remain pinned to their intended x-coordinates. The proof does not establish this claim. The text states 'the technicalities are tedious to show, but one can convince oneself by blowing up the construction' and later 'Again, the technicalities are tedious to show...', but no quantitative argument is provided to show that scaling or widening corridors prevents a coordinated shift of a frame component or that any such shift costs an extra wiggle. Because k is set exactly to kcr + 5|Γ|, even one unintended wiggle-saving deviation by the frame or a non-satisfying clause gadget would break the equivalence. Additionally, the accounting of kcr is ambiguous: if kcr counts all cross","section":"Section 4.2, Lemma 10 and definition of k"},{"comment":"The clause gadget is the heart of the reduction, and the 5-versus-6 wiggle gap between satisfied and unsatisfied clauses is exactly what sets the threshold k. However, the proofs of Lemmas 8 and 9 are given at the level of 'Figure 5 depicts such a nice coordination' and 'there is no nice coordination of the choice and blocking meetings such that ...', with no detailed case analysis. The role of the fixing characters, the shifted positions in the choice meetings, and the possible interactions between the three wire characters need a rigorous treatment. Since Lemma 10 depends directly on these lemmas, the NP-hardness proof cannot be considered complete without them.","section":"Section 4.2, Lemmas 8 and 9"},{"comment":"The exactness of the ILP formulation for WCMin rests on the assertion that Y = max{Δ,Δ} · Σ_t |AC(t)| is 'a trivial upper bound' for all y-coordinates. This is not proved and is not a consequence of the niceness constraints, because the wiggle-count objective does not penalize the magnitude of a displacement. For example, a single character active at two consecutive time steps, with no meeting constraints, can realize one wiggle with arbitrarily large displacement. Thus, while there may exist an optimal coordination inside the proposed bound, that fact requires proof. Without it, the ILP is not established as exact, and the WC optimum values reported in Table 1 from this ILP are not guaranteed to be true optima.","section":"Section 4.3, y-coordinate bound before the ILP"}],"minor_comments":[{"comment":"The notation π^{-1}(c) and π^{-1}(c′) is missing the subscript i; it should be π_i^{-1}(c) and π_i^{-1}(c′), consistent with Eq. (4).","section":"Section 4.1, Eq. (5)"},{"comment":"The symbol dx_t is used as the horizontal distance between consecutive time layers, but it is not formally defined in the text. Please define it explicitly and clarify that the LP in Section 5 optimizes dx_t^2 as a variable, not dx_t itself.","section":"Section 5, Eq. (8)-(9)"},{"comment":"References [9] and [11] appear to describe the same work with the same title and authors, and both contain the typo 'Minimzing wiggles'. The duplicated reference should be merged or distinguished clearly; the entry [10] is the corresponding master's thesis.","section":"References"},{"comment":"The introduction describes wiggle count as the number of inflection points, but Eq. (3) defines it as the number of time-step transitions in which a character's y-coordinate changes. These notions coincide only if every change of y is counted as one turn. Please make the definitional connection explicit.","section":"Section 2, wiggle count definition"},{"comment":"The table reports 'respective optimum' values for WC, LWH, QWH, and TH. It would be helpful to state explicitly which values are proven optimal and which are heuristic or incomplete (e.g., the t5 ILP entry marked with a superscript a and 'dnf'). The caption should clarify the status of each column.","section":"Section 6.1, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The central problem is exactly the one identified in the reading: Lemma 10's rigidity assertion is load-bearing and unproved, and the paper's own text admits this by saying 'one can convince oneself by blowing up the construction.' This is not a disagreement with the broader research direction; it is a missing proof of the main theorem. If the authors can supply the missing technicalities, the paper is likely a strong contribution. The Section 4.3 coordinate-bound issue is also worth attention because it affects the claimed exactness of the ILP and the experimental table. I would not recommend rejection if the proof gap is repairable, but the current manuscript does not support Theorem 5."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: if you are interested in storyline visualization algorithms, this is worth reading. The paper gives clean exact polynomial-time formulations for linear and quadratic wiggle height minimization, an ILP for wiggle count, and a genuinely new use case (rolling stock schedules). The LP/QP parts are formal and the integrality argument (Prop 1) is straightforward and convincing. The experimental comparison across 17 instances is honest, with solver times and a timeout noted. The new curve-routing LP is a nice practical touch.\n\nThe soft spot is exactly where the reader flagged it: Theorem 5, NP-completeness of WCMin, depends on Lemma 10, and Lemma 10's proof says 'the technicalities are tedious to show, but one can convince oneself by blowing up the construction.\" That is not a proof. The rigidity of the frame is load-bearing: the backward direction requires that no frame character wiggles and that gadgets stay pinned, and the budget k is tight (k_cr + 5|Gamma|). If a coordinated shift of a frame component saves even one wiggle, the equivalence collapses. The paper offers a sketch (widening corridors, scaling coordinates) but no formal argument that these blow-ups preserve the reduction. This is a real gap, not a stylistic complaint. The NP-hardness result might well be true, and the reduction strategy is plausible, but as written it is unproven.\n\nEverything else checks out. The polynomial cases (two time steps, wiggle-free subsets) are fine. The ILP formulation and its height penalty are reasonable. The case study visuals are nice, and the rolling stock connection is a genuine addition to the literature.\n\nWho should read this: anyone working on storyline layout algorithms, and possibly people in railway visualization. The hardness gap does not undermine the LP/QP contributions, so the paper deserves a serious referee. I would send it to review but explicitly ask the authors to either prove Lemma 10 or state it as a conjecture and adjust the claims. If the gap is fixed, this is a solid journal paper; as it stands it is a valuable paper with a missing proof in its central theorem.\n\nRecommendation: accept for peer review, flag the lemma.","headline":"Nice exact algorithms for two wiggle objectives and an honest experimental study, but the NP-hardness proof for wiggle count rests on an unproved rigidity lemma that needs real work before Theorem 5 can be trusted.","tokens_in":27157,"tokens_out":1658,"would_cite":true,"duration_ms":18196,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68U05","90C05","90C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Given fixed character orderings in a storyline, deciding whether the drawing can use at most k wiggles is NP-complete, while minimizing linear or quadratic wiggle height is polynomial-time solvable.","keywords":["storyline visualization","wiggle count minimization","NP-completeness","linear programming","quadratic programming","integer linear programming","curve routing","rolling stock schedules"],"falsifier":"Take a concrete small Planar Monotone 3-Sat formula, run the paper's construction, and search (by ILP or exhaustive enumeration) for a coordination with at most k wiggles in which a variable gadget is in the TRUE state while a positive wire is not satisfying, or in which frame characters shift; finding one would break Lemma 10's equivalence. Alternatively, a polynomial-time exact algorithm for WCMin would refute Theorem 5.","tokens_in":26360,"feed_emoji":"📉","tokens_out":6670,"duration_ms":70747,"temperature":0.7,"pith_summary":"This paper investigates how much character curves must move vertically in a storyline visualization, where each character is a curve over time and characters in the same scene at a given time are stacked consecutively. It proves that, once the vertical ordering of characters at every time step is fixed, minimizing the total number of wiggles (turns of a curve) is NP-complete, so no efficient exact algorithm is expected in general. At the same time, it shows that minimizing total wiggle height, either linearly or quadratically, can be done in polynomial time using a linear program and a convex quadratic program. The paper also contributes a curve-routing method that keeps neighboring character curves parallel with constant distances, and it demonstrates the three objectives on existing benchmarks and on railway rolling-stock schedules. This matters because crossings are not the only readability criterion for storylines; the amount and shape of vertical motion visibly affects whether the drawing looks calm or restless.","feed_headline":"Wiggle-count minimization in storylines is NP-complete","feed_subtitle":"Linear and quadratic wiggle height remain polynomial-time solvable, and new routing keeps curves smooth and parallel.","key_machinery":"The central objects are a storyline instance (characters, time steps, meetings, and an ordering of active characters at each time step) and a coordination, which assigns each character a y-coordinate at each time step so that meeting members are consecutive and equally spaced by Δ while non-meeting neighbors keep at least Δ distance. Wiggle count, wiggle height, and quadratic wiggle height are three metrics on a coordination. The proof machinery is a gadget reduction: variable gadgets whose characters have either |C_v| or 2|C_v| wiggles, clause gadgets that detect whether at least one wire character ends at its satisfying x-coordinate, and a rigid bounding frame intended to force coordinates","core_discovery":"On the paper's own terms, the main discovery is a complexity dichotomy inside one layout step. Given an ordered storyline instance—fixed character orderings at each time step, meetings marked as vertical bars—the decision problem of whether a nice coordination uses at most k wiggles is NP-complete (Theorem 5). The hardness is shown by a gadget reduction from Planar Monotone 3-Sat, with variable gadgets that can be in a TRUE or FALSE state, clause gadgets that force at least five wiggles unless one wire character is satisfying, and a rigid frame that is supposed to keep coordinates fixed. In contrast, the same instance can be solved in polynomial time for linear wiggle height by an LP and for","pith_inferences":["The authors leave the frame-rigidity verification to a blowing-up argument; formulating and checking the required local rigidity inequalities would make the reduction fully explicit and is a natural next step.","A testable consequence the paper does not spell out: the NP-hardness may be driven by the number of time steps, and the two-time-step result suggests the boundary is worth probing—exactly the fixed-parameter question the authors pose.","Because the same wiggle metrics appear in streamgraphs and stacked area charts, the LP and QP exact solutions may transfer to those chart types whenever the stacking order is fixed.","The routing LP suggests a possible joint optimization: alternate between choosing coordinates and choosing radii to reduce total drawing width, rather than fixing coordinates first."],"forward_implications":["No polynomial-time exact algorithm for minimizing wiggle count exists unless P = NP, so storyline layout pipelines that optimize crossings first must treat wiggle-count minimization as a hard subproblem.","Linear and quadratic wiggle height minimization are efficiently solvable exactly, and for integer minimum gaps the LP optimum can be taken integral, so the resulting drawings do not need rounding.","For just two time steps, minimizing wiggle count is polynomial (O(|C|^2)), and the largest set of characters that can be drawn without any wiggle can be found in O(|C|^2 ℓ) time.","The new curve routing turns each wiggle into two circular arcs with equal tangents, bounded radius, and monotone radial distance between co-oriented neighbors, which produces x-monotone, visually parallel curves.","Rolling stock schedules can be drawn as storylines, so wiggle and crossing minimization tools transfer to railway planning visualizations."],"supporting_citations":[{"why":"Supplies Planar Monotone 3-Sat, the NP-complete source problem for the wiggle-count reduction.","marker":"[6]"},{"why":"Introduces the four-step storyline pipeline and the heuristic reduction of wiggle count to weighted longest common subsequences, which the polynomial two-step and certificate arguments refine.","marker":"[19]"},{"why":"Establishes that linear programs are solvable in polynomial time, underpinning the efficiency claim for the linear wiggle height LP.","marker":"[15]"},{"why":"Establishes polynomial-time solvability of convex quadratic programs with linear constraints, underpinning the quadratic wiggle height QP.","marker":"[4]"},{"why":"Provides the exact crossing-minimization ILP used to produce ordered storyline instances for the benchmark.","marker":"[7]"},{"why":"Contributes the benchmark storylines used in the case study and earlier crossing-minimization methods.","marker":"[13]"},{"why":"Provides the streaming storyline instances used in the benchmark set.","marker":"[25]"},{"why":"Provides the rolling stock schedule dataset compared in the second case study.","marker":"[12]"}],"fun_headline_variants":["Wiggle count in storylines is NP-complete, height is easy","Storyline wiggle: count NP-complete, height polynomial","Minimizing wiggle count is NP-complete, height is polynomial-time","Wiggle optimization: count hard, height easy","For storylines, wiggle count is NP-complete, but height is easy"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is that the reduction's rigid frame really is rigid: no coordination within the allowed wiggle budget can shift frame characters, because the lower-bound argument that every good coordination needs at least k wiggles depends entirely on that, and the paper asserts this rigidity for a blown-up construction rather than proving it in full.","fun_headline_variants_meta":{"raw":{"variants":["Wiggle count in storylines is NP-complete, height is easy","Storyline wiggle: count NP-complete, height polynomial","Minimizing wiggle count is NP-complete, height is polynomial-time","Wiggle optimization: count hard, height easy","For storylines, wiggle count is NP-complete, but height is easy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00145,"raw_usage":{"total_tokens":5678,"prompt_tokens":749,"completion_tokens":4929,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":4845}},"tokens_in":493,"tokens_out":4929,"duration_ms":39984,"temperature":1.0,"reasoning_tokens":4845,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:27:32.173612+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete small Planar Monotone 3-Sat formula, run the paper's construction, and search (by ILP or exhaustive enumeration) for a coordination with at most k wiggles in which a variable gadget is in the TRUE state while a positive wire is not satisfying, or in which frame characters shift; finding one would break Lemma 10's equivalence. Alternatively, a polynomial-time exact algorithm for WCMin would refute Theorem 5.","supporting_citations":[{"cited_title":"Convex Optimization","cited_arxiv_id":null,"evidence_quote":"Establishes polynomial-time solvability of convex quadratic programs with linear constraints, underpinning the quadratic wiggle height QP."},{"cited_title":"u nger, Paul J. J \\","cited_arxiv_id":null,"evidence_quote":"Provides the exact crossing-minimization ILP used to produce ordered storyline instances for the benchmark."},{"cited_title":"An efficient framework for generating storyline visualizations from streaming data","cited_arxiv_id":null,"evidence_quote":"Provides the streaming storyline instances used in the benchmark set."},{"cited_title":"A comparison of two models for rolling stock scheduling","cited_arxiv_id":null,"evidence_quote":"Provides the rolling stock schedule dataset compared in the second case study."}],"review_version":1}