{"id":"d7113e71-d2e6-41b4-a1a9-eb0c126b7bf4","arxiv_id":"2411.15864","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Geometric thickness admits fixed-parameter algorithms for vertex cover and feedback edge number, while the extension problem is FPT for missing edges but W[1]-hard or NP-hard once vertices are also missing.","lead":"The paper studies how hard it is to draw a graph with straight-line edges in as few crossing-free layers as possible. It gives fast algorithms for some structured inputs and proves that extending a partially drawn solution is easy when only edges are missing but hard when vertices are missing too.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"XP-membership proof for GTE deletes a necessary collinearity constraint, so the ETR formula can accept spurious vertex-edge crossings.","rationale":"The reader identified Lemma 10 property (iii) and the Lemma 2 cell-count bound as the weakest points. I find a different, more concrete load-bearing issue in the XP-membership proof of Theorem 4. The paper's central claim includes the full parameterized characterization of Geometric Thickness Extension; the XP upper bound is half of that characterization. If the ETR encoding accepts invalid extensions due to the deletion of conjuncts with collinear fixed positions, the proof of XP-tractability fails as written. The issue is not merely a missing derivation but a concrete logical step that can be tested on a small instance: the strict sign test is actually correct for the deleted cases, so deleting those conjuncts is unnecessary and introduces false positives. This is a genuine correctness risk in a central theorem, and a concrete counterexample or a corrected proof is required. The FPT results in Sections 2, 3, and 5 appear solid, and the W[1]-hardness construction is detailed, so the overall verdict remains CONDITIONAL: the paper's main claims are plausible and likely fixable, but the XP-membership proof needs a substantive correction.","tokens_in":27321,"tokens_out":20299,"duration_ms":192175,"concrete_test":"Build a minimal GTE instance with fixed vertices a=(0,0), c=(-1,0), d=(1,0), drawn edge cd colored red, and one missing vertex b adjacent to a. Let ℓ=2 and force the only feasible color for ab to be red via local blocking triangles as in the paper's own gadget. Compute the ETR formula of Lemma 5, substitute the fixed positions and colors, and apply exactly the deletions described in the XP proof. Check whether the resulting formula is satisfiable: if it is, while no geometric 2-layer extension exists (because ab and cd touch at a), the proof's deletion step is invalid. An analytic version: verify that the conjunct containing a,b,c,d is the only one preventing the same-color assignment, so deleting it flips the formula's answer.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the XP-membership proof of Theorem 4 (Section 4), after substituting the fixed partial drawing into the ETR formula of Lemma 5, the authors delete every F3 conjunct that contains no free variables or 'precisely one free variable, where the other three predetermined positions are collinear.' This deletion is unsound for conjuncts that involve one missing vertex b, a drawn edge cd, and a fixed endpoint a of the new edge ab lying on the line through c and d. The original strict sign test in Lemma 5 remains correct in this case: F1 forces b off the line cd, so segments ab and cd intersect exactly when a lies between c and d, which is precisely when A(a,b,c)A(a,b,d) < 0. Deleting the conjunct removes this necessary restriction, so the relaxed formula may assign ab the same color as cd even though the two edges touch at a — a vertex-edge crossing. If all other colors for ab are blocked by the partial drawing, the formula becomes satisfiable although no valid extension exists, yielding a false positive. Thus the ETR encoding is not equivalent to GTE for non-general-position partial drawings, and the claimed XP-tractability is not established as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameterized complexity of computing geometric thickness (GT), where edges must be drawn as straight-line segments and partitioned into a minimum number of crossing-free layers. It contributes two FPT algorithms for GT, parameterized by vertex cover number (Theorem 1) and feedback edge number (Theorem 2), both obtained via kernelization. In the extension setting, it gives an FPT algorithm when only k edges are missing from a partial drawing (Theorem 3), an XP-algorithm plus W[1]-hardness when k edges and vertices are missing (Theorem 4), and NP-hardness when only two vertices are missing (Theorem 5). The paper thus claims a complete trichotomy for the extension problem depending on whether one parameterizes by missing edges, missing vertices, or both.","tokens_in":27521,"tokens_out":15942,"duration_ms":160226,"significance":"If the technical results are correct, this is a meaningful contribution: it provides the first parameterized algorithms for geometric thickness, a problem whose parameterized complexity had not been systematically addressed before. The extension-setting trichotomy is a clean and interesting structural result, and the FPT algorithm for missing edges is simple and elegant. The paper is largely self-contained, starting from explicit geometric characterizations and building the reductions from elementary constructions. The main results are false-or-true complexity statements with no fitted parameters, and the proofs of the two FPT kernelizations are plausibly correct modulo the issues below. The paper also identifies a natural open problem, GT parameterized by treewidth/treedepth, with a clear discussion of why standard dynamic-programming approaches fail. Provided the flagged technical gaps are repaired, the paper would merit publication.","major_comments":[{"comment":"The deletion rule for F3 conjuncts with exactly one free variable and three collinear predetermined positions is unsound. Consider a missing vertex b, a predrawn edge cd, and a predrawn vertex a lying on the line through c and d between c and d, with new edge ab. The original test A(a,b,c)A(a,b,d)>0 ∨ A(c,d,a)A(c,d,b)>0 is exact in this degenerate case: the second term is zero, but the first term is negative exactly when a lies between c and d, so the conjunct is necessary to forbid coloring ab the same as cd. Deleting it can turn an unsatisfiable instance into a satisfiable one, because the relaxed formula may accept a vertex-edge crossing at a. The proof must replace the blanket deletion with a case analysis or with an exact segment-intersection predicate for collinear configurations; as written, the claimed XP-membership is not established.","section":"Section 4 (XP-membership proof of Theorem 4)"},{"comment":"The cell-count bound used in the pigeonhole argument appears to be incorrect. The definition of C_{Γ,S}(v) in Definition 2 uses the half-planes H(v,a,b) whose boundary lines are the C(k',2) lines through pairs of vertices of S, not the k' lines through individual vertices. The bound of (k'^2+k'+2)/2 cited from Theorem 28.1.1 of [31] is the number of cells in an arrangement of k' lines, whereas the relevant arrangement has C(k',2) lines and can have O(k'^4) cells. Since the reduction rule's threshold is set to exceed the claimed cell count, the proof of Lemma 2 as written is not valid. The kernel-size statement can likely be repaired by raising the threshold to ℓ^{k'}·O(k'^4), which still gives ℓ^{O(k)} vertices for ℓ≥2, but the correction needs to be made explicitly.","section":"Section 2, Lemma 2"},{"comment":"Property (iii) of Lemma 10, which asserts that the color sets of the truth-assignment star and the verification star are disjoint in every valid extension, is supported only by a proof sketch ('the edges of t ... cut through the square vertically ... the visibility is blocked'). Section 7.1 does not provide the missing geometric derivation. Since Property (iii) is the central mechanism that prevents a satisfying assignment from being invalidated by shared colors, the NP-hardness reduction depends on it. A complete coordinate-based or otherwise rigorous proof of this property is required.","section":"Section 7, Lemma 10"}],"minor_comments":[{"comment":"In the XP-membership proof of Theorem 4, the definition of m' reads m' := |V(G)| - |V(H)|, but it should be |E(G)| - |E(H)|, the number of missing edges.","section":"Section 4"},{"comment":"The displayed runtime equality (9·O(n^4))^{O((2n'+m')^2)} = L^{O(1)}·n^{O(k)} is not correct as written; the left-hand side gives n^{O(k^2)}, which is still an XP bound, but the equality should be adjusted.","section":"Section 4"},{"comment":"The proof of Lemma 8 is described mostly by a construction sketch with forbidden segments and a scaling factor; for a journal version, more formal justification that the forbidden-segment lengths and the chosen s0 indeed guarantee a non-degenerate placement of all global blocking edges would help.","section":"Section 6.6"},{"comment":"Observation 3 states that the set of safe positions for moving a vertex is open, but the proof is deferred to the text; a short justification would improve readability.","section":"Section 1.2 / Observation 3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a serious parameterized-complexity contribution with plausible central claims, but the XP proof of Theorem 4 has a concrete soundness bug that needs a nontrivial fix, and the kernelization proof of Lemma 2 cites an incorrect cell-count bound. Both are load-bearing but appear repairable. The NP-hardness proof also needs a missing geometric derivation for Lemma 10(iii). I do not see evidence of a fatal flaw in the two FPT kernelizations or in the missing-edges FPT result, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Depian et al. give the first parameterized algorithms for geometric thickness, and that alone is worth a look. The FPT results for vertex cover number and feedback edge number are new, and the cloneability/kernelization argument in Lemma 1 is a genuine idea: within a cell, cloning a vertex is possible exactly when its admissible tie-region is nonempty. The feedback-edge kernel with path deletion is also clean. The extension trichotomy — FPT for missing edges, W[1]-hard with vertices also missing, NP-hard for two missing vertices — is a natural and mostly convincing classification.\n\nThe reader's take and the stress-test note are both on target. The XP upper bound in Theorem 4 has a real gap. The proof deletes every F3 conjunct with exactly one free variable where the other three predetermined positions are collinear. That is unsound. If a fixed endpoint a of a new edge ab lies on a drawn edge cd, then the original F3 conjunct is exactly what forbids coloring ab the same as cd when a sits between c and d. Deleting it lets the relaxed ETR formula accept a vertex-edge crossing. The authors need a more careful ETR encoding that handles non-general-position partial drawings by adding explicit non-collinearity or separation constraints instead of dropping conjuncts. This is fixable, but as written the XP-membership claim is not established.\n\nSmaller issues: Lemma 2's cell-count bound appears to count the arrangement of k' lines rather than the C(k',2) lines actually induced by the vertex cover; the correct bound is O(k'^4), and while the final ℓ^{O(k)} kernel size is unchanged, the threshold in the reduction rule needs updating. There is also a typo in the XP proof where m' is set to |V(G)|-|V(H)| instead of the edge difference.\n\nThe NP-hardness reduction for two missing vertices (Theorem 5) relies on a proof sketch in Lemma 10, especially property (iii) about disjoint color sets between the truth and verification stars. It looks plausible, but it needs a fuller geometric derivation, not just \"near completely cuts through\". The W[1]-hardness construction also has several \"elementary trigonometry\" steps that should be checked carefully.\n\nOverall: good paper, solid core, but revision needed. The FPT theorems and the hardness trichotomy are worth refereeing seriously. I would send it to a good graph drawing or parameterized complexity venue. Recommendation: engage with the paper, send it to peer review, and expect major revision focused on the XP proof.","headline":"First parameterized algorithms for geometric thickness, with a solid FPT core; the extension XP upper bound has a real gap that needs a fix.","tokens_in":5,"tokens_out":5645,"would_cite":true,"duration_ms":113327,"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":"Computing geometric thickness becomes fixed-parameter tractable for two structural parameters, and the extension problem is NP-hard with only two missing vertices.","keywords":["geometric thickness","straight-line drawings","parameterized complexity","kernelization","vertex cover number","feedback edge number","drawing extension","W[1]-hardness"],"falsifier":"Take the two-vertex reduction for a tiny unsatisfiable 3-SAT formula, such as the conjunction of $x$ and $\\neg x$, and solve the resulting Geometric Thickness Extension instance exactly by algebraic or exhaustive-rational means. The reduction claims the instance is negative; if a valid geometric extension is found, the proof of Theorem 5 fails at Lemma 10.","tokens_in":27086,"feed_emoji":"📐","tokens_out":11272,"duration_ms":93287,"temperature":0.7,"pith_summary":"This paper studies geometric thickness: the smallest number of crossing-free layers into which the edges of a straight-line drawing of a graph can be split. Because recognizing graphs of geometric thickness 2 is NP-hard, the authors ask which small structural parameters restore tractability, and they prove two fixed-parameter algorithms: one parameterized by the vertex cover number and one by the feedback edge number, both via kernels that shrink the instance to bounded size. For the natural extension problem, in which a partially drawn and edge-colored solution must be completed, they prove a complete complexity map: adding only $k$ missing edges is fixed-parameter tractable, adding $k$ missing vertices and edges together is XP-tractable but W[1]-hard, and already deleting just two vertices makes the problem NP-hard. These are the first parameterized algorithms for geometric thickness, and they locate exactly where the problem's intractability begins.","feed_headline":"Geometric thickness turns FPT for two structural parameters","feed_subtitle":"Vertex-cover and feedback-edge kernels make the problem feasible; extension stays hard even with two missing vertices.","key_machinery":"For the vertex-cover result the central object is the clone: two vertices outside the cover with identical neighborhoods and identically colored incident edges. Lemma 1 characterizes exactly when such a clone can be reinserted into its cell without creating a monochromatic crossing, and Lemma 2 combines that characterization with a bound on the number of cells induced by the cover and a pigeonhole argument to show that a large equivalence class of twins can always be shrunk. For the feedback-edge result the mechanism is a long path of degree-2 vertices drawn as a subdivided straight segment: if a path is much longer than the rest of the drawing, its subdivisions can absorb every monochromatic crossing, so the whole path can be removed. The hardness results are carried by choice gadgets, small red-triangle arrangements around anchor vertices that confine a missing vertex to one of several tiny disjoint disks, which the paper assembles around a regular $k$-gon with blocking edges to encode Multicolored Clique, and then reuses on a square with two stars whose edge colors must be disjoint for the two-vertex NP-hardness.","core_discovery":"The paper's own claims are: Geometric Thickness is fixed-parameter tractable when parameterized by the vertex cover number (Theorem 1) and by the feedback edge number (Theorem 2), with kernels of size $\\ell^{O(k)}$ and $O(10^k \\cdot 81^k)$ respectively. Geometric Thickness Extension is fixed-parameter tractable when only $k$ edges are missing (Theorem 3), is XP-tractable and W[1]-hard when $k$ counts both missing vertices and missing edges (Theorem 4), and is NP-hard even when exactly two vertices are missing from the provided partial drawing (Theorem 5). The W[1]-hardness of Theorem 4 holds even when the total number of layers is included in the parameter, and the two-vertex hardness is meant as a sharp contrast to earlier FPT results for extending other classes of drawings.","pith_inferences":["My inference: the choice-gadget machinery is not thickness-specific, so the same red-triangle blocking and disjoint-color argument may transfer to other geometric drawing-extension problems with layer or color constraints.","My inference: the vertex-cover kernel's dependence on $\\ell^{O(k)}$ comes from the cell-count bound; if that bound can be improved, the kernel could become independent of the number of layers, which would make Theorem 1 more directly usable.","My inference: the two-vertex NP-hardness leaves open whether the problem is $\\exists\\mathbb{R}$-complete; if the ETR formulation from Lemma 5 can handle pre-drawn vertices in the same way, the hardness could be strengthened beyond NP-hardness.","My inference: because Theorem 4 stays W[1]-hard even when the layer count is part of the parameter, the authors' open combination of vertex-plus-edge deletion distance with the layer count appears to be the most promising remaining parameterization for an FPT result."],"forward_implications":["If Theorem 1 is right, geometric thickness can be computed in time $f(k)n^{O(1)}$ for every graph whose vertex cover number $k$ is small, giving the first FPT algorithm for the problem.","If Theorem 2 is right, the same holds for graphs with small feedback edge number, a complementary structural parameter.","If Theorem 3 is right, any layered straight-line drawing missing at most $k$ edges can be completed in time $k^k n$, regardless of the number of layers.","If Theorem 4 is right, no FPT algorithm exists for completing drawings with $k$ missing vertices and edges unless FPT = W[1], even when the number of layers is added to the parameter.","If Theorem 5 is right, every algorithm parameterized by the number of missing vertices is ruled out unless P = NP, since the problem is hard already for two missing vertices."],"supporting_citations":[{"why":"Supplies the upper bound of $\\lceil k/2\\rceil$ on geometric thickness in graphs of treewidth $k$, used to remove the layer count from the vertex-cover parameterization.","marker":"[20]"},{"why":"Establishes NP-hardness of deciding geometric thickness 2, ruling out the thickness value itself as a tractable parameter.","marker":"[21]"},{"why":"Shows geometric thickness of multigraphs is $\\exists\\mathbb{R}$-complete, giving the decidability anchor used for kernelization and the ETR formulations.","marker":"[28]"},{"why":"Provides the arrangement-theoretic cell-count bound that the pigeonhole step of the vertex-cover kernel relies on.","marker":"[31]"},{"why":"Gives the existential-theory-of-reals decision algorithm used to prove XP-membership for the mixed missing-vertex-and-edge parameter.","marker":"[32]"},{"why":"Supplies the stack-layout extension technique that the two-vertex NP-hardness construction adapts to geometric thickness.","marker":"[16]"},{"why":"Provides the Multicolored Clique problem and parameterized-hardness framework used for the W[1]-hardness lower bound.","marker":"[15]"}],"fun_headline_variants":["Vertex cover and feedback edge numbers tame geometric thickness","Geometric thickness is FPT for two structural graph parameters","Thickness extension: FPT for missing edges, NP-hard for two vertices","Missing vertices make thickness extension hard, edges make it easy","Two new kernels make geometric thickness fixed-parameter tractable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the two-vertex NP-hardness construction really forces the two missing vertices into their intended regions and, crucially, that in every valid extension the color sets used by the truth-assignment star and the verification star are disjoint, which the paper only justifies with a proof sketch.","fun_headline_variants_meta":{"raw":{"variants":["Vertex cover and feedback edge numbers tame geometric thickness","Geometric thickness is FPT for two structural graph parameters","Thickness extension: FPT for missing edges, NP-hard for two vertices","Missing vertices make thickness extension hard, edges make it easy","Two new kernels make geometric thickness fixed-parameter tractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000393,"raw_usage":{"total_tokens":2029,"prompt_tokens":875,"completion_tokens":1154,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":491,"completion_tokens_details":{"reasoning_tokens":1071}},"tokens_in":491,"tokens_out":1154,"duration_ms":8478,"temperature":1.0,"reasoning_tokens":1071,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:50:09.099725+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the two-vertex reduction for a tiny unsatisfiable 3-SAT formula, such as the conjunction of $x$ and $\\neg x$, and solve the resulting Geometric Thickness Extension instance exactly by algebraic or exhaustive-rational means. The reduction claims the instance is negative; if a valid geometric extension is found, the proof of Theorem 5 fails at Lemma 10.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the upper bound of $\\lceil k/2\\rceil$ on geometric thickness in graphs of treewidth $k$, used to remove the layer count from the vertex-cover parameterization."},{"cited_title":"In: Soto, J.A., Wiese, A","cited_arxiv_id":null,"evidence_quote":"Shows geometric thickness of multigraphs is $\\exists\\mathbb{R}$-complete, giving the decidability anchor used for kernelization and the ETR formulations."},{"cited_title":"(eds.): Handbook of discrete and compu- tational geometry","cited_arxiv_id":null,"evidence_quote":"Provides the arrangement-theoretic cell-count bound that the pigeonhole step of the vertex-cover kernel relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the existential-theory-of-reals decision algorithm used to prove XP-membership for the mixed missing-vertex-and-edge parameter."}],"review_version":1}