{"id":"5f1810a5-3747-40c7-8a95-7ebc6e0f58a0","arxiv_id":"1908.08905","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Maximizing drawn edge length in partial edge drawings is NP-hard for 3-plane symmetric drawings and 4-plane general drawings, but becomes efficiently solvable when the edge-intersection graph has bounded treewidth.","lead":"This paper shows that choosing how much of each edge to draw while hiding all crossings is computationally hard even for graphs where each edge crosses only three or four other edges. It then gives fast algorithms for drawings whose crossing patterns form a tree or have bounded treewidth.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MaxPED NP-hardness proof in Appendix A uses an unformalized ε→0 limit and contains an inconsistent ink value; the reduction's iff is not yet established.","rationale":"The paper's positive results (tree and bounded-treewidth dynamic programs) are clearly argued and appear correct, and the experimental section provides supporting evidence for the algorithms. The headline claims, however, are the NP-hardness results: MaxSPED for 3-plane and MaxPED for 4-plane drawings. Theorem 1 is only sketched, and Theorem 2 is proved in Appendix A, which is the weaker link. The reader's weakest assumption already identified the ε-limit and the un-derived ink sums; my reading supports that concern and sharpens it. The proof explicitly works with l(s)+r(s)=1, i.e., zero-size gaps, and never fixes a positive ε that would make the drawings genuine PEDs. Moreover, the formula I(G(x))=|G(x)|(α+β) contradicts the stated segment length α+2β unless |G(x)| has an unusual meaning, and the clause-gadget maximum I(G(c))=221α+30β is asserted rather than derived; the internal component's contribution of 5α+6β out of 12α+6β is not justified. Because L is defined by adding these gadget maxima, any error here breaks the equivalence between ink ≥ L and satisfiability. These issues are fixable in principle by introducing a global ε and redoing the bookkeeping, but as written the proof is not complete. Hence the CONDITIONAL verdict is appropriate and my stress test does not change it.","tokens_in":17162,"tokens_out":26183,"duration_ms":266301,"concrete_test":"Implement a brute-force enumerator for the Appendix A gadgets: for a variable gadget (p segments of length α+2β with the stated intersections) and the clause gadget (three 4α+2β internal segments plus three 4-cycle weight components of 18α+2β segments), enumerate all ways of placing one positive gap per segment (with fixed ε≪β≪α and explicit coordinates) that hide every crossing, and compare the maximum ink with the claimed I(G(x))=p(α+β) and I(G(c))=221α+30β. If either maximum differs, Theorem 2's L-threshold is not correct as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central NP-hardness result for MaxPED (Theorem 2) rests on Appendix A, and that proof is not complete as written. First, the proof sets l(s)+r(s)=1 for every segment, i.e., it works with zero-size gaps, and encodes truth states via l(s)>r(s) versus r(s)>l(s). A genuine PED requires a positive erased gap, so the actual ink of a segment is |s|-ε; yet the threshold L is computed without any ε, and no argument shows that a single ε>0 works uniformly across all variable, wire, and clause gadgets. The limit ε→0 can change which configurations are valid, because stubs that merely touch at a crossing are treated as non-crossing. Second, the ink accounting is internally inconsistent: a variable-gadget segment is defined to have length α+2β, but the proof states I(G(x)) = |G(x)|(α+β), which is off by β per segment if |G(x)| counts segments. Similarly, I(G(c)) = 3·(72α+8β)+5α+6β = 221α+30β is asserted without deriving how the internal component (three segments of length 4α+2β each, total 12α+6β) can contribute only 5α+6β; the stated loss of 7α is not reconciled with the geometry (for example, erasing the α-middle sections of two segments would give 10α+6β, not 5α+6β). Since L is the sum of these gadget maxima, any error in these values breaks the equivalence I(D)≥L iff satisfiable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the ink-maximization problem for partial edge drawings (PEDs) and symmetric partial edge drawings (SPEDs) of k-plane straight-line drawings. The main theoretical contributions are: (1) NP-hardness of MaxSPED for 3-plane input drawings (Theorem 1), (2) NP-hardness of MaxPED for 4-plane input drawings (Theorem 2), (3) polynomial-time algorithms for both problems when the edge intersection graph of the drawing is a tree (Theorem 3 and Corollary 2), and (4) XP algorithms parameterized by the treewidth of the intersection graph (Theorem 4 and Corollary 3). The paper also reports a proof-of-concept implementation and experiments on spring and circular layouts. The algorithmic parts are clearly structured and the dynamic-programming recurrences appear correct. The hardness proof for MaxPED, however, is not complete as written: it relies on an unformalized ε→0 limit and contains internal inconsistencies in the ink accounting of the gadgets.","tokens_in":17496,"tokens_out":15596,"duration_ms":146699,"significance":"If the hardness results are established, they settle a conjecture of Bruckdorfer and close the complexity gap for MaxPED on k-plane drawings for k≥4, while also strengthening the known hardness of MaxSPED to 3-plane inputs. The treewidth-based algorithms are a genuine positive contribution: they give a clean XP parameterization and, for the forest case, simple polynomial-time dynamic programs that are also implemented and experimentally evaluated. The DP recurrences (Section 4) and the running-time analyses are presented in a way that is easy to verify, and the implementation is a useful proof of concept. The main weakness is the MaxPED NP-hardness proof in Appendix A, which is load-bearing for the paper's central claim and currently contains gaps that prevent the reduction from being considered rigorous.","major_comments":[{"comment":"The proof of Theorem 2 assumes l(s)+r(s)=1 for every segment, i.e., it works with zero-width gaps, and encodes truth states via which stub is longer. A genuine PED requires a positive erased gap, so the actual ink per segment is |s|-ε. The paper never proves that a single ε>0 works uniformly across all variable, wire, and clause gadgets, and the threshold L is computed without any ε. Since the set of valid configurations can change in the limit ε→0 (for example, stubs that merely touch at a crossing are treated as non-crossing), the equivalence I(D)≥L iff satisfiable is not established by the argument as written.","section":"Appendix A, first paragraph"},{"comment":"The ink accounting for the variable gadget is internally inconsistent. The segment length is defined as |s_i|=α+2β, and it is stated that G(x) admits a PED with I(G(x))=Σ|s_i|, but the proof then asserts I(G(x))=|G(x)|·(α+β). If |G(x)| denotes the number of segments, this is off by β per segment; if it denotes something else, that quantity is never defined. Since L is defined as the sum of gadget maxima, this discrepancy propagates into the wire-loss analysis and the correctness argument.","section":"Appendix A, variable gadget"},{"comment":"The claimed maximum ink value of the clause gadget, I(G(c)) = 3·(72α+8β)+5α+6β = 221α+30β, is asserted without a derivation of the 5α+6β internal contribution. The internal component consists of three segments of total length 12α+6β, so the claimed loss of 7α from the internal component is not reconciled with the geometry. In particular, the argument that placing the gap of an internal segment anywhere other than at its weight-component intersection loses 'at least 9α units of ink' is not substantiated, and the text does not explain why the configuration achieving 5α+6β is valid while alternative configurations are not. Because the threshold L and the reduction's iff depend on this value, the proof is incomplete.","section":"Appendix A, clause gadget"},{"comment":"The converse direction of the MaxSPED reduction is dismissed with 'it is straight-forward to verify that the corresponding truth assignment satisfies φ'. Given the complexity of the variable and clause gadgets and the wire connections, the proof needs an explicit case analysis showing that any SPED with ink at least L forces each variable gadget into one of its two states and each clause gadget to be satisfied. As written, this is a gap in the proof of Theorem 1, although less severe than the MaxPED issues in Appendix A.","section":"Section 3.1, Theorem 1"}],"minor_comments":[{"comment":"There is a typo: 'we can draw s0 of G(x,c) with its gap at the intersection with s1' should presumably be 's1' rather than 's0', since the wire segments are indexed s1,...,sz.","section":"Appendix A, final paragraph"},{"comment":"The caption says 'a maximum-ink SPED (b) of the same graph', but the surrounding text and the context (Section 3.2 / Appendix A) concern PEDs, not SPEDs; this should be corrected to avoid confusion.","section":"Figure 7 caption"},{"comment":"The notation |G(x)| is used ambiguously: it is not defined whether it denotes the number of segments, the total length, or something else. This ambiguity contributes to the accounting inconsistency noted above.","section":"Appendix A, variable gadget"},{"comment":"There is a typo: 'an increase by a of factor 1.5' should be 'an increase by a factor of 1.5'.","section":"Section 5, experiments"}],"recommendation":"major_revision","confidential_remarks":"The paper is a revised arXiv version, and the MaxPED hardness proof in Appendix A still contains the serious gaps described in the major comments. The high-level reduction idea is plausible and may be repairable, but the current text does not establish the central NP-hardness claim. I would encourage the editor to request a thorough rewrite of Appendix A with a complete, self-contained proof, including a positive-epsilon argument and a full derivation of all gadget ink values, before considering the paper for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the algorithmic half is solid and worth having, and the MaxSPED hardness theorem is credible. The MaxPED hardness theorem (Theorem 2) is not proven as written—Appendix A's epsilon abstraction and ink accounting need real work before that result is citable.\n\nWhat's new: they strengthen MaxSPED NP-hardness to 3-plane drawings and claim MaxPED NP-hardness for 4-plane, which would settle a conjecture from Bruckdorfer's thesis. The tree and bounded-treewidth dynamic programs are correctly derived, and the implementation plus experiments are honest and appropriately brief. Related-work claims check out against Bruckdorfer et al. and the thesis; citations are background, not load-bearing. This part deserves publication.\n\nThe soft spot is Appendix A, and the reader's and stress-test concerns land. The proof sets l(s)+r(s)=1, i.e., zero-size gaps, and says truth states are preserved by which stub is longer. But a real PED requires a positive gap, and the threshold L is computed without any epsilon. The paper never argues that a single epsilon>0 works uniformly across variable, wire, and clause gadgets, and in the limit stubs that merely touch at a crossing count as non-crossing. That is a real gap in the equivalence I(D)>=L iff satisfiable.\n\nThe ink accounting is asserted rather than derived, and at least one value looks inconsistent with the stated geometry: a variable-gadget segment has length alpha+2beta, yet the gadget optimum is |G(x)|(alpha+beta), off by beta per segment. The clause maximum, 221alpha+30beta, is declared without derivation, and I cannot reconcile the internal component's 5alpha+6beta with the described segment lengths. These may be typos or a different intended geometry; either way, a referee cannot verify the threshold L, and the reduction's iff depends on it. The converse of Theorem 1 is also dispatched as 'straight-forward'—minor, but a referee should ask for the induction.\n\nNet: algorithms publishable now; hardness results likely correct and important for the subfield. As submitted, Theorem 2 needs a rewritten appendix with a formal epsilon (explicit bounds) and step-by-step ink accounting for every gadget. Whether the paper settles Bruckdorfer's conjecture depends on that repair. This is for the graph-drawing crowd—PED researchers and anyone doing treewidth DP on intersection graphs—and the algorithm sections are directly usable.\n\nRecommendation: send it to peer review. A serious referee should spend time on Appendix A; if the authors fix it, this is a solid paper, and if they cannot, the MaxPED hardness claim should be withdrawn rather than published. I would cite the treewidth algorithms; I would not cite the hardness result from this arXiv version. I'd bring it to a reading group to discuss the epsilon limit.","headline":"Sound treewidth algorithms plus a credible but incomplete MaxPED hardness proof; Appendix A needs a formal epsilon argument and corrected ink arithmetic before the complexity claim is citable.","tokens_in":17992,"tokens_out":13121,"would_cite":true,"duration_ms":119782,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R10","68U05","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves exact ink-maximization for partial edge drawings is NP-hard once crossings per edge reach three (SPED) or four (PED), and gives polynomial/XP algorithms when the edge-intersection graph is a tree or has bounded treewidth.","keywords":["partial edge drawings","ink maximization","symmetric partial edge drawings","k-plane graphs","NP-hardness","treewidth","dynamic programming","edge intersection graph"],"falsifier":"Set alpha = 2 beta in the Theorem 2 gadgets and exhaustively enumerate all stub/gap placements for one variable gadget and one clause gadget, computing the true maximum ink by brute force; the reduction requires the variable gadget's per-segment maximum to be alpha + beta, the clause gadget's maximum to be 221 alpha + 30 beta, and any placement that gains 3 alpha by drawing a connecting section to lose at least 9 alpha in the attached weight component, so any configuration exceeding these totals would break the threshold L.","tokens_in":16943,"feed_emoji":"✏️","tokens_out":9703,"duration_ms":96510,"temperature":0.7,"pith_summary":"Partial edge drawing erases the middle of each edge so the two remaining stubs hide all crossings; ink maximization asks how much total stub length can be kept while preserving this property. The paper proves that maximizing ink is NP-hard even when every edge crosses at most three other edges (for symmetric stubs) or four (for general stubs), closing a gap left by earlier work. On the positive side, it gives exact algorithms that run in polynomial time when the graph recording which edges cross is a forest, and in time exponential only in the treewidth of that graph otherwise. The upshot is a structural dichotomy: hardness appears at small constant crossing counts, but tractability can be recovered from the shape of the crossing graph.","feed_headline":"Ink maximization is NP-hard at 3-plane and 4-plane drawings","feed_subtitle":"Erasing edge middles to hide crossings: deciding how much ink can be kept is hard, but tree-like crossings stay solvable.","key_machinery":"The central object is the edge intersection graph C of the drawing: a vertex for every drawn edge and an edge for every crossing. Since the drawing is k-plane, C has maximum degree k. The finite-state insight is that a segment s(u) with delta_u crossings has only delta_u + 1 relevant stub-length choices (the lengths cut off at successive intersection points, plus the full segment). The tree algorithm stores W_i(u), the best ink in the subtree of C when s(u) is drawn with the i-th stub length, and separates child contributions into short(v) (choices that do not constrain the parent) and long(v) (those that do). The bounded-treewidth algorithm stores W(t,S) for each node t of a nice tree decomposition: S is a valid choice of stubs on the bag X_t, and W(t,S) is the best ink in V_t consistent with S, combined through leaf, introduce, forget, and join recurrences. All of the work, both hardness and tractability, flows from the fact that only these finitely many stub lengths per edge matter.","core_discovery":"The paper establishes two complexity thresholds. For symmetric partial edge drawings, deciding whether a given straight-line drawing admits a solution with ink at least L is NP-hard already for 3-plane input drawings, where no edge crosses more than three others; the reduction uses planar 3-SAT, with variable gadgets that have exactly two maximum-ink states (encoding true/false) and clause gadgets that reach their maximum ink only when at least one literal is satisfied. For general (asymmetric) partial edge drawings, the same decision problem is NP-hard for 4-plane input drawings; because the stubs are independent, the construction works with an arbitrarily small erased gap per edge and uses the position of that gap to encode truth values, with a clause gadget whose weight components make it too expensive to draw more than one full triangle segment. Complementing these hardness results, the paper gives exact dynamic programs for both problems when the edge intersection graph is a tree, with running times O(mk + m log m) and O($mk^{2}$ + m log m), and XP algorithms when that graph has treewidth at most omega, with running times exponential only in omega. Corollary: neither problem is fixed-parameter tractable when parameterized by the crossing number k alone.","pith_inferences":["By extension, the same finite stub-choice DP should solve fixed-ratio asymmetric homogeneous PEDs on trees and bounded-treewidth crossing graphs; the paper names this as an expected but unresolved direction.","Because the MaxPED hardness proof lets the erased gap shrink to zero, a natural stress test is to recompute the reduction with one fixed positive gap size; if no single epsilon works for every gadget, the hardness threshold could depend on the gap, not just on k.","The dichotomy suggests a practical heuristic: even drawings with many crossings can be solved exactly whenever the crossing graph is near-forest, so an exact solver should measure treewidth first and fall back to heuristics only when treewidth is large."],"forward_implications":["MaxSPED has no polynomial algorithm for 3-plane drawings unless P = NP; together with the known polynomial algorithm for 2-plane drawings, this puts the tractability threshold exactly at k = 2 for symmetric stubs.","MaxPED is NP-hard for 4-plane drawings; the 3-plane case remains open, and Corollary 1 rules out fixed-parameter tractability by k alone for both problems.","If the edge intersection graph is a tree, maximum-ink SPEDs and PEDs can be computed exactly in O(mk + m log m) and O(mk^2 + m log m) time, respectively.","If the intersection graph has treewidth at most omega, both problems are solvable in time exponential only in omega: O(m(k+1)^{omega+2} omega^2 + m log m) for MaxSPED and O(m(k+1)^{omega+3} omega^2 + m log m) for MaxPED.","The implemented treewidth algorithm preserves, on the tested layouts, roughly 84-90% of the ink for SPEDs and 97-99% for PEDs, showing that the exact optimum leaves only moderate erasure on those instances."],"supporting_citations":[{"why":"Establishes the 2-plane polynomial case and the previous state of the art that the hardness results extend.","marker":"[6]"},{"why":"Defines PEDs and SPEDs, gives the ILP formulation, and provides the epsilon-gap observation used in the MaxPED construction.","marker":"[7]"},{"why":"Contained a sketch of MaxSPED NP-hardness and conjectured MaxPED hardness; this paper supplies the full reductions.","marker":"[5]"},{"why":"Supplies planar 3-SAT, the NP-hard problem both reductions start from.","marker":"[17]"},{"why":"Provides the treewidth dynamic-programming template and adjacency data structure adapted by the algorithms.","marker":"[13]"},{"why":"Provides the nice tree decomposition framework used in the bounded-treewidth algorithms.","marker":"[14]"},{"why":"Defines treewidth, the parameter governing the tractable cases.","marker":"[19]"}],"fun_headline_variants":["Ink max: NP-hard at 3-plane, but tree-like crossings are tractable","NP-hard even at 3-plane, but forest-like intersections solve exactly","Hard at 3-plane, easy on tree-like: ink maximization thresholds","Ink in PEDs: NP-hard at 3-plane, polynomial on tree intersections"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hardness proofs assume the exact ink values assigned to each gadget are correct and that the tiny erased gap in the MaxPED construction can be made uniformly small enough that no other configuration overturns the claimed optimum; if that accounting fails, the equivalence between high-ink drawings and satisfying truth assignments collapses.","fun_headline_variants_meta":{"raw":{"variants":["Ink max: NP-hard at 3-plane, but tree-like crossings are tractable","NP-hard even at 3-plane, but forest-like intersections solve exactly","Hard at 3-plane, easy on tree-like: ink maximization thresholds","Ink in PEDs: NP-hard at 3-plane, polynomial on tree intersections"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00096,"raw_usage":{"total_tokens":4121,"prompt_tokens":1006,"completion_tokens":3115,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":3027}},"tokens_in":622,"tokens_out":3115,"duration_ms":21392,"temperature":1.0,"reasoning_tokens":3027,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:29:08.242294+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set alpha = 2 beta in the Theorem 2 gadgets and exhaustively enumerate all stub/gap placements for one variable gadget and one clause gadget, computing the true maximum ink by brute force; the reduction requires the variable gadget's per-segment maximum to be alpha + beta, the clause gadget's maximum to be 221 alpha + 30 beta, and any placement that gains 3 alpha by drawing a connecting section to lose at least 9 alpha in the attached weight component, so any configuration exceeding these totals would break the threshold L.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the 2-plane polynomial case and the previous state of the art that the hardness results extend."},{"cited_title":"(eds.) Fun with Algorithms (FUN’12)","cited_arxiv_id":null,"evidence_quote":"Defines PEDs and SPEDs, gives the ILP formulation, and provides the epsilon-gap observation used in the MaxPED construction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contained a sketch of MaxSPED NP-hardness and conjectured MaxPED hardness; this paper supplies the full reductions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the treewidth dynamic-programming template and adjacency data structure adapted by the algorithms."}],"review_version":1}