{"id":"b3b9f46b-fb68-46b9-8115-5e51c2924bcd","arxiv_id":"2506.10717","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"k-Planarity Testing stays NP-hard and hard to approximate on graphs with tiny feedback vertex sets, while becoming fixed-parameter tractable and kernelizable under vertex cover or treedepth parameters.","lead":"This paper maps when k-planarity testing is easy or hard depending on simple graph shape measures, and proves that even very tree-like graphs can make the problem NP-complete or inapproximable. It also gives fast algorithms and small kernels for graph classes with small vertex cover or treedepth.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 11 states that the Theorem 9 graph is near-planar and has pathwidth at most 4, but neither property is proved; the abstract's headline strengthening of Cabello–Mohar depends directly on these assertions.","rationale":"We reviewed the paper in good faith. The main algorithmic claims (FPT for feedback edge set, treedepth+k, kernels) are supported by proofs in the body or appendix; Lemma 1, Lemma 2, and the kernelization Lemma 21 are sketched but plausible, and the appendix fills many details. The hardness reductions from Two-Sided k-Planarity and Unary Bin Packing are coherent, and the fvs≤2 claim in Theorem 5 follows from removing uX,uY and subdividing. The weakest point is exactly the reader's: Corollary 11 asserts near-planarity and pathwidth≤4 for the Theorem 9 graph with no proof. This is load-bearing because it is the advertised strengthening over Cabello–Mohar and Urschel–Wellens in the abstract. It is not an internal inconsistency: the claims are likely true, and a short proof may exist. However, as written, the central headline is conditional on an unproved structural assertion. We therefore agree with the reader's CONDITIONAL verdict and see no reason to move it. The concrete test above would either produce the missing proof or expose a counterexample.","tokens_in":17653,"tokens_out":19868,"duration_ms":242080,"concrete_test":"Verify the missing structural lemma for the graph G of Theorem 9: (1) show that G−e is planar for every edge e of the cycle C, or at least exhibit one such e with a planar embedding; (2) show that the following bags form a path decomposition of width ≤4: process the cycle C in cyclic order, take bags {u1,u2,vi,vi+1} for each consecutive pair, and insert each path Pj one vertex at a time using bags {u1,u2,p_t,p_{t+1}}. As a computational cross-check, instantiate the construction for b=3, B=4, S={1,2,2,3,4}, test planarity of G−e for all edges with a linear-time planarity tester, and compute pathwidth exactly by brute force; any failure falsifies the claim, and success indicates the missing proof is recoverable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single most load-bearing gap is in the passage immediately before Corollary 11: 'Theorem 9 strengthens their hardness result as the graph G constructed in the reduction is a near-planar graph with the following properties.' No proof is given for either advertised property. Near-planarity requires exhibiting an edge e such that G−e is planar; pathwidth ≤4 requires a path decomposition of width 4. These are not obvious from the reduction: the construction in Theorem 9 interleaves the cycle C through v1,...,vb, two hub vertices u1,u2 with many subdivided spokes, and paths Pj whose vertices are all adjacent to both u1 and u2, so the claimed bounds need real argument. If either assertion fails, the NP-completeness result for near-planar graphs with fvs≤3 and pw≤4, which is the abstract's headline, is not established, even though the W[1]-hardness of distance to path forest and the fvs≤2 inapproximability could still stand. The statement may be true (deleting an edge of C plausibly makes the graph planar, and a width-4 decomposition with bags {u1,u2,vi,vi+1} plus one path vertex per bag is plausible), but the paper supplies no verification, so the advertised strengthening rests on an unproved structural claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies structural parameterizations of k-Planarity Testing and the local crossing number. It presents NP-hardness and inapproximability results for 1-planarity and local crossing number on graphs with feedback vertex set number 2 or 3, including near-planar graphs with pathwidth at most 4; W[1]-hardness results for treedepth, twin cover, and distance to path forest; and FPT algorithms and polynomial kernels parameterized by feedback edge set, treedepth+k, vertex cover, and neighborhood diversity. The positive results are accompanied by proofs in the appendix, and the negative results are obtained from reductions from Two-Sided k-Planarity and Unary Bin Packing.","tokens_in":17859,"tokens_out":18500,"duration_ms":205792,"significance":"If the results hold, the paper substantially sharpens known lower bounds: it improves the NP-completeness of 1-planarity on near-planar graphs to those with fvs ≤ 3 and pathwidth ≤ 4, and the (2−ε)-inapproximability of local crossing number to any constant factor on graphs with fvs ≤ 2. It also provides several tight FPT and kernelization results for the general k ≥ 1 case. The reductions are mostly explicit and the appendix contains detailed proofs of several technical lemmas. However, the central structural claims behind the headline lower bound are currently asserted rather than proved.","major_comments":[{"comment":"Corollary 11 asserts that the graph G built in Theorem 9 is near-planar and has pathwidth at most 4, but neither property is proved anywhere in the text. The abstract's headline strengthening of the Cabello–Mohar result depends directly on these assertions; the authors should give an explicit edge e such that G−e is planar and an explicit path decomposition of width 4, and they should also state the (easy but currently implicit) argument that fvs(G) ≤ 3.","section":"3.2, before Corollary 11"},{"comment":"In the proof of Theorem 6, the sentence 'the reduction used in Lemma 4 increases the treedepth by at most 3' is stated without justification. Since the W[1]-hardness with respect to treedepth is transferred through this reduction, a construction of an elimination forest of height td(G') ≤ td(G)+3 (or a precise reference) should be supplied.","section":"3.1, Theorem 6"},{"comment":"The reverse direction of the proof of Theorem 9 relies on the assertion that in the crossing-free spoke subdrawing there are two vertices v_i and v_j that lie on the outer cycle and all other v_ℓ are drawn inside the region bounded by that outer cycle. This is a topological claim about the planar subdrawing induced by the spokes and is not formally established; without it the extraction of the b regions and the counting argument do not follow. Please provide a proof or a precise citation.","section":"3.2, Theorem 9 (reverse direction)"}],"minor_comments":[{"comment":"In the proof of Theorem 13, 'add ℓ2 := B(bℓ1 + m) + 1 spokes between u2 and v2' should read 'between u2 and vi'; as written, the construction would not define b regions.","section":"3.3, Theorem 13 proof"},{"comment":"In Lemma 19, the phrase 'degree at least 2 in V(G)\\S' is confusing because V(G)\\S is independent; it should say 'degree at least 2 in G' (or 'in S').","section":"4.2, Lemma 19"},{"comment":"If the proof of Corollary 11 is added, please also state whether the pathwidth bound of 4 is tight or merely an upper bound, since the current wording suggests a tight structural bound.","section":"Abstract / Corollary 11"},{"comment":"The proof of Lemma 4 is terse in its topological parts, especially in the construction of the closed curve C satisfying properties (4) and (5); adding a few more details about how the cyclic order of the edges incident to u is used would improve readability.","section":"3.1, Lemma 4"}],"recommendation":"major_revision","confidential_remarks":"The main algorithmic results appear sound and the lower-bound results are plausible, but the central advertised strengthening (Corollary 11) is not yet supported by a proof. The paper also cites [25], an overlapping-author paper, for the NP-hardness of Two-Sided k-Planarity on trees; I would encourage the authors to verify that the cited theorem is precisely the stated one in the published version and to make the dependence explicit. I would be willing to re-review a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Probably the most useful thing to know: this is a genuinely new and coherent mapping of k-planarity testing across structural parameters, and most of the load-bearing results are likely correct. The two headline lower bounds—constant-factor inapproximability on fvs≤2 and NP-completeness on near-planar graphs with fvs≤3 and pw≤4—rest on reductions from external problems. The first one (Theorem 8) is built on the Two-Sided k-Planarity reduction plus a black-box inapproximability result for bandwidth, which is solid. The second (Corollary 11) is the one I would scrutinize: the paper asserts without proof that the graph constructed in the Unary Bin Packing reduction is near-planar and has pathwidth at most 4. The claim may be true—deleting an edge of the outer cycle plausibly makes it planar, and a width-4 decomposition can be guessed—but it is not shown, and the abstract's headline strengthening of Cabello–Mohar depends directly on those two assertions. This needs to be fixed before publication.\n\nWhat is new and good: the paper gives the first polynomial kernels for general k (vertex cover and neighborhood diversity), FPT algorithms for feedback edge set and treedepth+k, and W[1]-hardness for treedepth, twin cover, and distance to path forest. The kernelization core (Lemma 21) is the right kind of technical work: a counting argument over paths in a 1-planar drawing, with a proof that is sketchy in places but plausible. The appendix does contain real proofs for several deferred lemmas, so the paper is not just promises.\n\nSoft spots, in proportion: Corollary 11 unproved (major for the advertised headline, minor for the rest of the paper). Theorem 6 states the reduction increases treedepth by at most 3 without justification; given W[1]-hardness of Bandwidth by treedepth is the source, this needs a short proof. Lemma 2 and Lemma 12 are proof sketches; the latter is a standard padding trick, but the former's uncrossing argument deserves a careful write-up.\n\nOn citations: [16] and [25] are co-authored by the current authors, but they are published SoCG/TCS results, not private communications, and no circularity is apparent. Nothing here looks like data fitting or invented targets.\n\nBottom line: this paper belongs in the literature. It deserves a serious referee who can verify the two missing structural claims. If those are supplied, I would accept without hesitation. For a reading group, it is a good example of how to build a parameterized landscape, though you may want to warn people to read Corollary 11 skeptically.\n\nRecommendation: send to peer review, with a request for the missing proofs.","headline":"A solid and genuinely new map of k-planarity across structural parameters, but the abstract's headline strengthening rests on two asserted-and-unproved structural properties that need fixing.","tokens_in":18438,"tokens_out":4175,"would_cite":true,"duration_ms":40589,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that testing 1-planarity is NP-complete on near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and that local crossing number is hard to approximate within any constant factor even on…","keywords":["1-planar graphs","local crossing number","beyond planarity","parameterized complexity","kernelization","treedepth","pathwidth","feedback vertex set"],"falsifier":"Construct an explicit path decomposition of width at most 4 for the graph in the proof of the paper's Theorem 9, and name one edge whose deletion leaves it planar. If neither can be produced, the near-planar pathwidth-4 NP-completeness statement is unsupported.","tokens_in":1759,"feed_emoji":"📐","tokens_out":2459,"duration_ms":120334,"temperature":0.7,"pith_summary":"This paper is about where the intractability of k-planarity testing begins. It shows that deciding whether a graph can be drawn with at most one crossing per edge is NP-complete even for graphs obtainable from a planar graph by adding a single edge, with feedback vertex set number at most 3 and pathwidth at most 4. It also proves that the local crossing number has no polynomial-time constant-factor approximation unless P = NP, even for graphs that become forests after deleting two vertices. On the algorithmic side, it establishes fixed-parameter tractability for treedepth plus k, feedback edge set number, and path-free graph classes, and gives polynomial kernels for vertex cover and neighborhood diversity. The net effect is a near-complete map of which structural parameters make the problem tractable and which do not.","feed_headline":"1-planarity stays NP-complete on near-planar, pathwidth-4 graphs","feed_subtitle":"Hardness now squeezes into constant-treewidth near-planar graphs, and approximation fails inside tiny deletion sets.","key_machinery":"The main workhorses are two reductions. A subdivision lemma states that $\\mathrm{lcr}(G) \\le k$ if and only if the graph obtained by subdividing every edge $k-1$ times is 1-planar, which converts general $k$ to the already-studied 1-planarity case with only a logarithmic treedepth blow-up and with feedback edge set number unchanged. A 'spoke' gadget, consisting of many internally disjoint length-2 paths from a new vertex to each vertex of a selected set, forces all spokes to be crossing-free in any $k$-planar drawing; this lets the paper import hardness from two-sided (2-layer) $k$-planarity and from Unary Bin Packing while keeping structural parameters tiny. The kernelization rests on counting twin classes and on a reduction rule for degree-2 vertices with identical neighborhoods, bounded by the $k$-planar edge bound and by the fact that $K_{7k+1,3}$ is not $k$-planar.","core_discovery":"The central claim is that the hardness boundary for k-planarity testing sits much lower than previously known. Testing 1-planarity is NP-complete even when the input graph is near-planar (planar plus one edge), has feedback vertex set number at most 3, and has pathwidth at most 4. Separately, the local crossing number cannot be approximated within any constant factor in polynomial time unless P = NP, even for graphs whose feedback vertex set number is at most 2. On the positive side, the paper proves fixed-parameter tractability for treedepth plus k, for feedback edge set number, and for $P_t$-free graphs parameterized by $t+k$, and gives polynomial kernels for vertex cover number and neighborhood diversity. It also proves W[1]-hardness for treedepth alone, twin cover number, and distance to path forest, so the positive treedepth result is tight in requiring $k$ as part of the parameter.","pith_inferences":["Editorial inference: the unproved near-planarity and pathwidth claims in the paper's Corollary 11 are directly checkable from the construction; supplying an explicit path decomposition of width 4 and a single deletable edge would settle the strongest advertised result.","Editorial inference: the spoke gadget is a flexible forcing device, so the same many-parallel-length-2-paths construction could plausibly be reused to prove hardness for other drawing models or other width parameters such as bounded vertex integrity or shrub-depth.","Editorial inference: the subdivision lemma implies that future FPT or hardness results for 1-planarity automatically transfer to k-planarity with only a logarithmic penalty in treedepth, so progress on general k can largely be routed through the better-studied k = 1 case."],"forward_implications":["1-planarity testing remains NP-complete on constant-treewidth near-planar graphs, so any polynomial algorithm for that class must handle both the one-edge deviation from planarity and width at most 4 simultaneously.","Unless P = NP, there is no constant-factor approximation for the local crossing number even when deleting just two vertices makes the graph a forest.","k-planarity testing is FPT in treedepth plus k and in feedback edge set number, so these parameters give genuine tractability once k is charged to the parameter.","The problem admits polynomial-size kernels for vertex cover and neighborhood diversity, with explicit $O(\\mathrm{vc}(G)^2 k^2 \\sqrt{k})$ and $O(\\mathrm{nd}(G)^2 k^3 \\sqrt{k})$ bounds, computable in linear time.","k-planarity is W[1]-hard parameterized by treedepth alone, so the FPT treedepth-plus-k result cannot drop the $+k$ term unless W[1] = FPT."],"supporting_citations":[{"why":"Established NP-completeness of 1-planarity on near-planar graphs, which the present paper strengthens by adding feedback vertex set and pathwidth constraints.","marker":"[4]"},{"why":"Gave the previous $(2-\\varepsilon)$-inapproximability for local crossing number, which the paper improves to any constant factor.","marker":"[33]"},{"why":"Contributed the FPT algorithms for 1-planarity under treedepth and feedback edge number that the paper extends to general k.","marker":"[2]"},{"why":"Showed NP-completeness of Two-Sided k-Planarity on trees, the source of the feedback-vertex-set-2 hardness.","marker":"[25]"},{"why":"Provided W[1]-hardness of Unary Bin Packing parameterized by the number of bins, used in the distance-to-path-forest reduction.","marker":"[22]"},{"why":"Supplied NP-completeness of Unary Bin Packing and of Crossing Number, which the reductions rely on.","marker":"[15]"},{"why":"Gave the edge bound for k-planar graphs used in bounding the kernel sizes.","marker":"[1]"},{"why":"Provided NP-membership for 1-planarity testing, used in the NP-completeness arguments.","marker":"[26]"}],"fun_headline_variants":["1-planarity NP-complete on near-planar, pathwidth-4 graphs","Even pathwidth-4 near-planar graphs keep 1-planarity NP-complete","1-planarity NP-complete with feedback vertex set ≤3 and pathwidth ≤4","Local crossing number hard to approximate even on feedback-vertex-set-2 graphs"],"cache_read_input_tokens":20608,"weakest_assumption_plain":"The load-bearing premise is that the graph built in the Bin Packing reduction is genuinely near-planar and has pathwidth at most 4; the paper states both facts without giving a proof.","fun_headline_variants_meta":{"raw":{"variants":["1-planarity NP-complete on near-planar, pathwidth-4 graphs","Even pathwidth-4 near-planar graphs keep 1-planarity NP-complete","1-planarity NP-complete with feedback vertex set ≤3 and pathwidth ≤4","Local crossing number hard to approximate even on feedback-vertex-set-2 graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001718,"raw_usage":{"total_tokens":6853,"prompt_tokens":1061,"completion_tokens":5792,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":677,"completion_tokens_details":{"reasoning_tokens":5704}},"tokens_in":677,"tokens_out":5792,"duration_ms":50018,"temperature":1.0,"reasoning_tokens":5704,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:21:19.654108+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct an explicit path decomposition of width at most 4 for the graph in the proof of the paper's Theorem 9, and name one edge whose deletion leaves it planar. If neither can be produced, the near-planar pathwidth-4 NP-completeness statement is unsupported.","supporting_citations":[{"cited_title":"31 János Pach and Géza Tóth","cited_arxiv_id":null,"evidence_quote":"Showed NP-completeness of Two-Sided k-Planarity on trees, the source of the feedback-vertex-set-2 hardness."},{"cited_title":"27 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Jie Xue, and Meirav Zehavi","cited_arxiv_id":null,"evidence_quote":"Provided W[1]-hardness of Unary Bin Packing parameterized by the number of bins, used in the distance-to-path-forest reduction."}],"review_version":1}