{"id":"6c2603da-90be-4d5a-8464-83cd7ef886f3","arxiv_id":"2412.04042","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives XP algorithms for recognizing 2-layer and outer k-planar graphs, proves both problems XNLP-hard, and gives an FPT algorithm for the one-sided 2-layer variant.","lead":"Two new algorithm families recognize 2-layer and outer k-planar graphs in polynomial time for every fixed k, and a matching hardness result shows these problems are unlikely to be fixed-parameter tractable. The paper settles a long-standing question about outer 2-planar graphs and clarifies the complexity of drawings with few crossings per edge.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Outer k-planarity XP algorithm depends on Lemma 13, which is only justified by a same-author lemma for maximal graphs; no proof shows the splitting property carries over to the non-maximal subproblem G_{τ,e,R}. If Lemma 13 fails, Theorem 12 collapses.","rationale":"We read the paper in good faith and agree with the reader's identification of the weakest assumption. The central contribution is the outer k-planar XP algorithm; its recurrence (Lemma 14) relies on Lemma 13 to guarantee a splitting vertex in every valid drawing. The proof of Lemma 13 is a star-reference to [25, Lemma 6], an external same-author result on maximal outer k-planar graphs. The claim that maximality is unused is plausible but unverified in the text: the subproblem graph contains degree-1 t_i vertices and lacks outer-cycle edges, and the desired vertex must lie in R rather than in the t-arc. This is structurally distinct from the recognition claim, but it is load-bearing: if Lemma 13 fails, the DP can reject valid inputs. We also noticed that the proof of Claim 20 in Lemma 15 contains a questionable assertion ('each path ... must cross the piercing edge'), but the stated bound follows from a different standard argument (the edge from u to the rightmost neighbor is crossed by one edge from each other path), so we do not treat that as the primary concern. No code or formal verification is provided, so the external lemma is the only support for the key structural split. The verdict should remain conditional pending an independent check of Lemma 13.","tokens_in":24729,"tokens_out":30004,"duration_ms":277122,"concrete_test":"Independently re-derive [25, Lemma 6] and instantiate its active-link splitting argument on G_{τ,e,R} for a non-maximal outer k-planar graph: verify that the proof does not require the outer-cycle edges {u,t1}, {ti,ti+1}, {tℓ,v}, that the degree-1 placeholder vertices t_i do not break the charging argument, and that the vertex w obtained lies in R. If the argument cannot be adapted without maximality, or if the only guaranteed w lies among the t_i, Lemma 13 is unsupported and Theorem 12 is unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 13 is the engine of the Outer k-Planarity XP algorithm: the recurrence in Lemma 14 enumerates splits at a vertex w∈R whose pairs with u and v are each pierced by at most k edges. If no such w exists in some valid drawing, then draw(u,v,R,τ,χ) can be false even though a valid outer k-planar drawing satisfying P1/P2 exists, so the DP would reject a YES instance. The proof of Lemma 13 is entirely delegated to [25, Lemma 6], a paper that shares two authors with this one. The transfer is not demonstrated: [25] works on maximal outer k-planar graphs, whose outer-cycle edges exist and carry no crossings, whereas G_{τ,e,R} need not contain {u,t1}, {ti,ti+1}, or {tℓ,v}, and the t_i are degree-1 placeholder vertices. The proof states 'they did not use the maximality ... to show the existence of such an index j,' but no argument is given that the active-link splitting produces a vertex on the R-arc rather than among the placeholder t_i, or that the charging argument survives without the outer cycle. Thus the central open-problem result is only as secure as an unverified external lemma.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameterized complexity of recognizing two families of graphs with bounded local crossing number: 2-layer k-planar graphs (bipartite graphs drawable on two parallel lines with at most k crossings per edge) and outer k-planar graphs (drawable on a circle with at most k crossings per edge). The main positive results are an XP-algorithm for Two-Sided k-Planarity running in 2^{O(k^3)} n^{2k+O(1)} time (Theorem 9) and an XP-algorithm for Outer k-Planarity running in 2^{O(k log k)} n^{3k+O(1)} time (Theorem 12), the latter resolving the open problem of polynomial-time recognition of outer 2-planar graphs. The paper also gives an FPT algorithm for One-Sided k-Planarity (Theorem 3), shows XNLP-completeness/hardness for the two-sided and outer variants (Theorems 11 and 19), proves weak NP-hardness for weighted one-sided variants, and derives an inapproximability result for the local circular crossing number on graphs with feedback vertex number 1 (Theorem 16). Most proofs are deferred to an appendix, and some key arguments are given only as sketches or by reference to an accompanying paper.","tokens_in":24955,"tokens_out":9134,"duration_ms":91338,"significance":"If the results are correct, this is a substantial contribution: it settles a natural open problem in beyond-planar graph recognition, gives the first recognition algorithms that are polynomial for every fixed k for both 2-layer k-planar and outer k-planar graphs, and places the corresponding problems in the parameterized hierarchy between XP and W[t]-hardness. The algorithmic ideas are clearly valuable: the one-sided FPT algorithm, the Saxe-style localization argument for the two-sided case, and the split recurrence for outer k-planar graphs are elegant and concrete. The paper also contains explicit running time bounds and several negative results that complement the positive ones. However, the outer k-planar XP algorithm rests on a lemma whose proof is delegated to a same-author paper and whose hypotheses are not verified in the present setting; this is load-bearing for Theorem 12.","major_comments":[{"comment":"The proof of Lemma 13 is not self-contained and the transfer from [25, Lemma 6] is not demonstrated. The text says only that the authors of [25] 'did not use the maximality of G to show the existence of such an index j', and then applies the argument directly. But the graph G_{\\vec e,R,\\tau} is not maximal, has no outer cycle, and contains degree-one placeholder vertices t_1,...,t_\\ell between u and v. The active-link argument in [25] operates on a maximal outer k-planar graph whose outer cycle edges exist and carry no crossings; none of these facts is established for G_{\\vec e,R,\\tau}. In particular, the recursive splitting of the pair {u,v} could produce an index j corresponding to one of the placeholder vertices t_i, which is not an element of R and therefore cannot be used as the vertex w required by Lemma 14. Since Lemma 14 is the engine of the XP algorithm for Outer k-Planarity, the proof of Theorem 12 is incomplete without a full proof of Lemma 13 or a precise reduction to [25, Lemma 6] that verifies all hypotheses, including why the selected vertex lies in R.","section":"Appendix, Lemma 13"},{"comment":"The reduction to biconnected graphs is asserted without proof for general k: 'a graph is outer k-planar if and only if its biconnected components are outer k-planar; this can be shown in a similar manner as [32, Theorem 4] for k = 2.' This statement is used to justify restricting the input to biconnected graphs, and Theorem 12 depends on it. A proof or a reference that covers all k should be supplied, since the decomposition of an outer k-planar drawing at cut vertices is not entirely trivial when edges incident to the cut vertex may cross edges inside different blocks.","section":"Section 5.1, first paragraph"},{"comment":"The enumeration bound in Lemma 15 is proved only as a sketch. The step 'Since R is a union of components in the graph obtained from G[V(G)\\setminus{u,v}] by deleting the piercing edges' needs more justification: it must be shown that every R that appears as a feasible subproblem for a fixed pair {u,v} arises in this way from some valid drawing, and that distinct drawings cannot force a super-exponential number of candidate sets R beyond the counted 2^d component unions. This is less severe than the Lemma 13 issue, but it is used in the running time analysis of Theorem 12 and should be written out in full.","section":"Appendix, Lemma 15"}],"minor_comments":[{"comment":"The recurrence uses the symbol \\bigvee without a formal definition; please state explicitly that it denotes the logical OR over the listed choices for D_{i-1} and \\chi_{i-1}.","section":"Section 3.1, Lemma 5"},{"comment":"The theorem says 'no polynomial-time c-approximation algorithm for Outer k-Planarity', but Outer k-Planarity is a decision problem. Please state that the inapproximability concerns the local circular crossing number, i.e., the minimum k for which the graph admits an outer k-planar drawing.","section":"Section 5.2, Theorem 16"},{"comment":"The phrase 'Property P1 ... assures that {u,v} has \\ell \\le k piercing edges' is not immediate from the definition of piercing and should be justified explicitly, especially because {u,v} need not be an edge.","section":"Appendix, Lemma 13"},{"comment":"There is a typo in the converse direction: 'Supposethatthereareconsistent' should be split into separate words. Additionally, the proof of the converse says 'It is not difficult to see' when combining D_H, D_1, and D_2; a sentence explaining why no new crossing exceeds k would improve readability.","section":"Appendix, Lemma 14"},{"comment":"In the inequality for 2k, the case b=0 is not meaningful because k is defined via division by 2 and the reduction assumes b\\ge 1 implicitly; please state this explicitly to avoid a minor edge-case ambiguity.","section":"Section 4.2, Theorem 11 proof"}],"recommendation":"major_revision","confidential_remarks":"The main risk is Lemma 13: the proof is a hand-wave to a same-author paper, and the placeholder vertices t_i make the transfer non-obvious. If the authors supply a complete, self-contained proof of Lemma 13 and a proof for the biconnected decomposition for arbitrary k, I would view the paper as a strong contribution. I would not recommend rejection based on the current evidence, since the rest of the algorithm is carefully structured and the concern is local to one lemma, but the central claim of the paper currently rests on an unverified external statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper resolves a real open problem: outer 2-planar recognition in polynomial time, and more generally gives XP algorithms for two-sided 2-layer and outer k-planarity, plus XNLP-hardness complements and an FPT algorithm for the one-sided case. The two-sided algorithm (Theorem 9) and the split-at-a-vertex recurrence (Lemma 14) are the genuine contributions here, and the writers clearly know the parameterized-complexity landscape. The FPT one-sided algorithm is clean and uses a nice degree-reduction argument. This is solid work, not a token extension of known techniques.\n\nThe softest spot is exactly where the stress-test points: Lemma 13, the engine of the outer k-planar XP algorithm, is proved by reference to [25, Lemma 6] from a same-author paper. The appendix says the maximality was not used, but the transfer is not shown. In the subproblem G_{\\tau,e,R}, you do not have the outer-cycle edges, and the placeholder vertices t_i are degree-1, so the active-link charging argument from a maximal graph does not obviously survive. The authors do provide a sketch of why the proof transfers, but it is terse. Given that Theorem 12 collapses if Lemma 13 fails, this deserves a full proof in the paper. I would not call it a fatal flaw—the lemma is plausible and the sketch gives a path—but it is a genuine gap that a referee must push on.\n\nMinor issues: the biconnected decomposition at the start of Section 5.1 is asserted without proof for general k (the cited proof is for k=2), and Lemma 18's counting is loose but correct. The XNLP-hardness proofs rely on standard reductions and look right; the tree case for Two-Sided is a nice touch. No code or data, which is normal.\n\nWho this is for: graph drawing and parameterized complexity people. The paper deserves a serious referee; the central claims are significant and mostly well-supported. My recommendation is to send it to review, but the referee should demand a self-contained proof of Lemma 13 and a proof or explicit citation for the biconnected reduction.","headline":"Strong XP/FPT results for 2-layer and outer k-planar recognition, with the main proof gap being Lemma 13's reliance on an external same-author lemma that the authors do not fully transfer.","tokens_in":25533,"tokens_out":566,"would_cite":true,"duration_ms":7377,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","05C85","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives polynomial-time algorithms, for every fixed k, to recognize graphs that can be drawn with all vertices on two parallel lines or on a circle with at most k crossings per edge.","keywords":["2-layer k-planar graphs","outer k-planar graphs","recognition algorithms","local crossing number","parameterized complexity","XP algorithms","XNLP-hardness","bandwidth"],"falsifier":"Find a biconnected outer k-planar graph in which some consecutive pair (u,v) has the property that for every third vertex w, at least one of the pairs {u,w} and {v,w} is pierced by more than k edges in every outer k-planar drawing; such a graph would make Lemma 13 false and break the split recurrence behind Theorem 12.","tokens_in":24493,"feed_emoji":"📐","tokens_out":5889,"duration_ms":48204,"temperature":0.7,"pith_summary":"The paper establishes that two natural recognition problems from graph drawing, one where vertices must lie on two parallel lines and one where they must lie on a circle, become polynomial-time solvable when the local crossing bound k is any fixed constant. In both settings an edge may cross at most k other edges. This settles a question left open in earlier work: outer 2-planar graphs can be recognized in polynomial time. The paper also shows that both problems are unlikely to have fixed-parameter-tractable algorithms, and that the variant with one prescribed layer order is fixed-parameter tractable.","feed_headline":"Two local crossing-number problems are in P for every fixed k","feed_subtitle":"XP algorithms settle outer 2-planar recognition and map the limits of FPT for 2-layer and circular drawings.","key_machinery":"The load-bearing machinery is a separator-based splitting recurrence. For the two-layer problem, a set of 2k+1 consecutive vertices on one layer acts as a window; Lemma 8 shows that any connected component of the graph outside this window lies entirely to the left or entirely to the right, which lets the algorithm decompose the instance exactly as in the classical dynamic-programming technique for recognizing small-bandwidth graphs. For the outer problem, Lemma 13 guarantees that any consecutive pair (u,v) has a third vertex w such that both pairs {u,w} and {v,w} are pierced by at most k edges; the algorithm splits the instance into two smaller subinstances with pairs (u,w) and (w,v), recomputing crossing counts through a consistency condition that encodes the crossings inside the triangle formed by u, v, and w.","core_discovery":"For each fixed k, Two-Sided k-Planarity and Outer k-Planarity are in XP: the first is solved in time $2^{{O(k^3)}}$ $n^{{2k+O(1)}}$ and the second in time $2^{{O(k log k)}}$ $n^{{3k+O(1)}}$. The algorithms are dynamic programs that split a candidate drawing around small separators, a consecutive window of 2k+1 vertices on one layer for the two-layer case, and a third vertex that separates a circular drawing for the outer case. The paper further proves that Two-Sided k-Planarity is XNLP-complete even on trees, that Outer k-Planarity is XNLP-hard, and therefore that both are W[t]-hard for every t and unlikely to admit FPT algorithms under standard parameterized-complexity conjectures. For the one-sided version, where the order of one layer is part of the input, the paper gives an FPT algorithm running in $2^{{O(k log k)}}$ $n^{{O(1)}}$ time.","pith_inferences":["Beyond the paper, the same separator-splitting scheme may extend to ℓ-layer k-planarity parameterized by ℓ+k, which the authors list as an open problem.","Beyond the paper, making explicit the tree decomposition implicitly constructed by the outer k-planar dynamic program could connect these XP results with the known quasi-polynomial recognition algorithm for outer k-planar graphs.","Beyond the paper, the bandwidth-based hardness reductions suggest that many local crossing-number variants with vertex-order constraints inherit hardness from linear-arrangement problems, so one might predict similar XNLP-hardness for related fixed-order book-embedding settings.","Beyond the paper, one could empirically test Lemma 13 for small k by exhaustively checking random outer k-planar drawings, which would provide computational evidence for the split recurrence before the companion triangulation lemma is fully formalized."],"forward_implications":["Outer 2-planar graphs can be recognized in polynomial time, answering the open problem posed by the authors of the linear-time outer 1-planar recognition algorithm.","For every fixed k, both 2-layer k-planar and outer k-planar recognition are in P, though the polynomial exponents grow with k.","The XNLP-hardness results imply that neither recognition problem is FPT with respect to k unless the parameterized complexity hierarchy collapses in a way the community regards as unlikely.","When the order of one layer is given, the one-sided 2-layer problem is FPT, so the fixed-order setting is genuinely easier than the two-sided one.","The local circular crossing number cannot be approximated within any constant factor in polynomial time, even for graphs that have feedback vertex number one."],"supporting_citations":[{"why":"Supplies the triangulation lemma (Lemma 6 there) whose proof is followed to establish Lemma 13, the existence of a split vertex w in any outer k-planar drawing.","marker":"[25]"},{"why":"Introduces the dynamic-programming scheme for recognizing small-bandwidth graphs in polynomial time, which the two-sided 2-layer algorithm adapts through consecutive vertex windows.","marker":"[44]"},{"why":"Gives the linear-time recognition of outer 1-planar graphs and explicitly poses polynomial-time recognition of outer 2-planar graphs as an open problem.","marker":"[31]"},{"why":"Provides the biconnected-component reduction used at the start of the outer k-planar section and the linear-time recognition of full outer 2-planar graphs.","marker":"[32]"},{"why":"Establishes the O(sqrt(k) n) edge bound for outer k-planar graphs, which bounds m in the runtime of Theorem 12.","marker":"[41]"},{"why":"Defines the XNLP class and states that XNLP-hard problems are W[t]-hard for every t, the implication used for the hardness interpretation of both recognition problems.","marker":"[14]"},{"why":"Shows that Bandwidth is XNLP-hard even on trees, which is the source problem for the parameterized logspace reductions in Theorems 11 and 19.","marker":"[11]"},{"why":"Gives the inapproximability of Bandwidth on trees used in the reduction proving constant-factor inapproximability of Outer k-Planarity in Theorem 16.","marker":"[22]"}],"fun_headline_variants":["XP algorithms settle outer 2-planar recognition","Two local crossing problems: XP algorithms, XNLP-hardness","Outer and 2-layer k-planarity: XP but not FPT","Fixed k: 2-layer and outer k-planar graphs in XP","One-sided 2-layer k-planarity is FPT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The outer k-planar algorithm rests on Lemma 13, which says that in any outer k-planar drawing, a consecutive pair (u,v) always has a third vertex w such that both pairs {u,w} and {v,w} are pierced by at most k edges; the proof imports the corresponding statement from a triangulation lemma in a companion paper, so if that lemma does not cover non-maximal drawings, the splitting recurrence collapses.","fun_headline_variants_meta":{"raw":{"variants":["XP algorithms settle outer 2-planar recognition","Two local crossing problems: XP algorithms, XNLP-hardness","Outer and 2-layer k-planarity: XP but not FPT","Fixed k: 2-layer and outer k-planar graphs in XP","One-sided 2-layer k-planarity is FPT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000583,"raw_usage":{"total_tokens":2854,"prompt_tokens":1166,"completion_tokens":1688,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":782,"completion_tokens_details":{"reasoning_tokens":1600}},"tokens_in":782,"tokens_out":1688,"duration_ms":78474,"temperature":1.0,"reasoning_tokens":1600,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T21:53:03.459707+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a biconnected outer k-planar graph in which some consecutive pair (u,v) has the property that for every third vertex w, at least one of the pairs {u,w} and {v,w} is pierced by more than k edges in every outer k-planar drawing; such a graph would make Lemma 13 false and break the split recurrence behind Theorem 12.","supporting_citations":[{"cited_title":"Bounding the Treewidth of Outer $k$-Planar Graphs via Triangulations","cited_arxiv_id":"2408.04264","evidence_quote":"Supplies the triangulation lemma (Lemma 6 there) whose proof is followed to establish Lemma 13, the existence of a split vertex w in any outer k-planar drawing."},{"cited_title":"A linear-time algorithm for testing outer-1-planarity","cited_arxiv_id":null,"evidence_quote":"Gives the linear-time recognition of outer 1-planar graphs and explicitly poses polynomial-time recognition of outer 2-planar graphs as an open problem."},{"cited_title":"A linear-time algorithm for testing full outer-2-planarity","cited_arxiv_id":null,"evidence_quote":"Provides the biconnected-component reduction used at the start of the outer k-planar section and the linear-time recognition of full outer 2-planar graphs."}],"review_version":1}