{"id":"a43787d5-ecb8-4f33-98cc-1fc2316ba463","arxiv_id":"2607.24182","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"List-constrained point-set embeddability is poly-time or FPT for connected graphs on convex points, but NP-hard already for bi-labeled matchings (convex) and bi-labeled paths (general), with matching FPT/paraNP dichotomies by vertex cover and list size.","lead":"The paper fully maps the complexity of drawing a graph with straight lines onto a finite point set when each vertex is restricted to a short list of allowed points. It settles an open question on binary trees and draws a tight tractability boundary that graph-drawing algorithms and hardness proofs can now use.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"The flagged soft spot — the greedy exchange in Claim 3.8 / Case 2 of Theorem 3.2 — is the right place to look, but on close reading it appears to hold: the \"first point\" definition of T gives optimal substructure for free, and Property 1 makes the greedy case split exhaustive. No objection lands.","rationale":"The reader correctly located the only argument in the paper whose compression could hide a real gap: the greedy left-to-right composition of block realizations in Claim 3.8 and Case 2 of Theorem 3.2. My stress test of that spot, however, strengthens rather than weakens the paper. Two mechanisms do the work that the reader's missing \"exchange lemma\" would have done: (i) all table entries and intermediate quantities q_i are defined as minima (\"the first point q ... such that\"), so any competing realization's endpoint is automatically ≥ the computed one, giving optimal substructure without an exchange argument; (ii) the seemingly lossy move of restarting block B_{i+1} at p_v+1 when p_v falls inside its minimal interval is safe because any realization spanning p_v without occupying it forces a block edge crossing the p_v position, which Property 1 excludes — and the callers only need Property-1-respecting realizations for their crossing-free augmentations. So the reader's hypothetical counterexample configuration (non-greedy earlier placement freeing a shorter later interval) is ruled out by the definitions themselves.\n\nI also probed the other candidates for a load-bearing flaw and found only surface issues: the 2SAT encoding in Lemma 4.3 has a presentation gap (the correctness proof for crossing C–C edges invokes unit clauses that ϕ4 as displayed does not contain), the two-star reduction (Theorem 4.6) has list/edge typos, and the Grid Tiling corridor arithmetic in Section 5.2 is sketched with a worst-case slope argument whose bound (ε < 1/(2η)) is conservative enough to survive the sloppiness. None of these touch the central claims.\n\nAccordingly: no change to ACCEPT. The one verification still worth running is a brute-force differential test of ALG1 on small instances, which would settle the greedy-DP concern definitively and cheaply, and would also incidentally exercise the p_v-inside-interval branch that my analysis says is the only subtle spot.","tokens_in":28405,"tokens_out":6619,"duration_ms":153270,"concrete_test":"Implement ALG1 (the O(n·ℓ·s) DP) and an exhaustive brute-force enumerator of all list-respecting placements on small convex point sets. On random instances with s ≤ 10, connected planar G with n ≤ 8 (including cutvertices and varied block-cut-tree shapes), a fixed outerplanar embedding, and random lists with ℓ ≤ 3, compare YES/NO answers. Stress the delicate branch: bias instances so that some cutvertex v has a list point strictly inside the minimal interval of a child block. The dangerous failure direction is DP = NO while brute force finds a realization; a single such instance would falsify Claim 3.8. Also verify each finite computed T[B,p] against the brute-forced minimum endpoint.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I agree with the reader that the only place where the central algorithmic claims (Theorem 3.2) could quietly break is the greedy interval computation in Claim 3.8 and its use in Case 2. I tried to construct the counterexample the reader worries about — a non-greedy placement of an earlier block that frees a shorter later interval — and it fails for a structural reason the paper states but does not spell out as a lemma: T[B,p] and the q_i are defined as the *first* (minimum) endpoint admitting a realization. Hence for any competing realization of the same subproblem, its endpoint q̃ satisfies q̃ ≥ T[B, start] automatically; and since a larger start index only shrinks the feasible window, starting the next block at the minimal q_i can never be worse. Optimal substructure is thus baked into the table definition rather than requiring a separate exchange lemma.\n\nThe genuinely delicate case is when p_v ∈ [q_i+1, T[B_{i+1}, q_i+1]], where the algorithm restarts block B_{i+1} at p_v+1. The only way this could lose a valid solution is if B_{i+1} could be realized spanning across p_v without occupying it, ending earlier than T[B_{i+1}, p_v+1]. But any connected block occupying points on both sides of p_v must contain an edge with one endpoint before and one after p_v, which violates Property 1 of Claim 3.8 — and the callers (Case 1 and Case 2) only ever rely on realizations satisfying Property 1, so the exclusion is internally consistent. The case split is exhaustive.\n\nResidual concerns are minor: Lemma 4.3's ϕ4 as written only quantifies over pairs in U, yet the correctness proof invokes clauses forbidding a single U-placement crossing a C–C edge (unit clauses ¬x_{u,p} seem intended but not displayed); and Theorem 4.6 / Section 5.2 contain typos (duplicated list entry, duplicated edge, \"2ε-wide corridors\"). None of these threaten the headline claims. Overall I cannot identify a load-bearing flaw; this is close to an honest non-finding, with the greedy DP remaining the one co","agreement_with_reader":"agree"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper does what a good theory paper should: it takes a classical problem, adds the natural list constraint, and maps the complexity almost completely. The headline results are real. On convex point sets they get NP-hardness already for bi-labeled matchings (and height-2 trees), then a clean poly-time DP for connected graphs with a given combinatorial embedding and an FPT algorithm in maximum degree without one. That last piece directly answers Frati et al.’s open question on binary trees and disproves the suspected hardness. On general point sets the picture flips: bi-labeled paths and cycles become hard, yet bi-labeled graphs stay FPT by vertex cover, with a matching paraNP-hardness already for two tri-labeled stars. The APX-hardness of the max-edge variant and the W[1]/FPT dichotomy for partial extension round it out. The landscape figure is genuinely useful.\n\nWhat they do well is the gadgetry and the block-cut-tree DP. Reductions from Planar Monotone 3-SAT, Grid Tiling, and MAX-2SAT(3) are spelled out with explicit geometry and bidirectional arguments. The convex algorithm is detailed enough (recurrences, hand-shaking runtime, back-links) that you can check it. The stress-test concern about the greedy exchange in Claim 3.8 / Case 2 does not land: the “first point” definition of the table already encodes optimal substructure, and Property 1 makes the case split exhaustive. No counter-example configuration survives.\n\nSoft spots are minor and local. Lemma 4.3’s ϕ4 as written only ranges over pairs in U, while the proof text also needs unit clauses against C–C crossings; a couple of typos appear in the two-star and Grid-Tiling sections. None of that touches the main claims. Citations are standard and light on self-reference.\n\nThis is for people who work on geometric graph drawing, parameterized algorithms for layout, or point-set embeddability. If that is your area you will cite the dichotomy theorems. It deserves a serious referee; I would accept it for peer review without hesitation.","headline":"Clean complexity map for list-constrained point-set embeddability that settles the GD’13 open question and draws a sharp convex-vs-general split.","tokens_in":30128,"tokens_out":539,"would_cite":true,"duration_ms":15707,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"List-constrained point-set embeddability is polynomial for connected graphs on convex points once an embedding is fixed, yet NP-hard for bi-labeled matchings and for paths on general points.","keywords":["point set embedding","list constraints","parameterized algorithms","NP-hardness","dynamic programming","graph drawing","computational geometry","vertex cover"],"falsifier":"An explicit convex instance whose shortest outerplanar realization places some earlier block non-greedily and thereby frees a strictly shorter total interval than the dynamic program reports.","tokens_in":29742,"feed_emoji":"📐","tokens_out":851,"duration_ms":20619,"temperature":0.7,"pith_summary":"The paper studies whether a graph can be drawn with straight-line edges and no crossings when each vertex may sit only on a short list of allowed points from a finite set. On points in convex position the answer is still NP-hard for the simplest graphs (matchings or height-2 trees) once every list has size at most two, but becomes polynomial-time solvable for any connected graph that already carries a combinatorial embedding and fixed-parameter tractable in maximum degree when the embedding is free. On arbitrary point sets the same problem is NP-hard already for bi-labeled paths and cycles, yet fixed-parameter tractable in the vertex-cover number for bi-labeled instances; three labels per vertex make even two stars hard. The same boundary appears in the natural optimization and partial-drawing-extension variants. The results give a nearly complete complexity map that separates the geometric setting from the combinatorial one and answers a concrete open question left by earlier work on bi-colored trees.","feed_headline":"List point-set drawing is poly-time on convex points with embedding","feed_subtitle":"Connected graphs become easy once rotation systems are fixed; paths stay hard on general points","key_machinery":"A dynamic program on the block-cut tree that greedily computes shortest feasible intervals for successive child blocks (Claim 3.8 and the two cases of Theorem 3.2), relying on free interchangeability of the root cut-vertex outside each occupied interval.","core_discovery":"When the host point set is convex, connectivity plus a prescribed combinatorial embedding is enough to decide list-constrained straight-line embeddability in polynomial time, while dropping either condition immediately yields NP-hardness; on general point sets the same decision problem collapses to NP-hardness even for paths of maximum degree two.","pith_inferences":["The same block-cut dynamic program may extend, with only minor changes, to outerplanar graphs that are disconnected once the number of components is treated as an additional parameter.","Hardness for bi-labeled paths already rules out FPT algorithms under almost every classical structural parameter on general point sets, so future positive results must either restrict geometry further or move to approximation.","The APX-hardness reduction suggests that even constant-factor approximation of the maximum number of embeddable edges is unlikely unless the lists are of size one."],"forward_implications":["Binary trees on two-colored convex point sets are polynomial-time embeddable, settling the open question of Frati et al.","Any FPT algorithm for general point sets must exploit a parameter at least as strong as vertex cover once lists may have size three.","Maximizing the number of straight-line edges under bi-label constraints admits no PTAS even for graphs of vertex-cover number two.","Partial drawings become fixed-parameter tractable once both the number of free vertices and the surplus of unused points are bounded."],"fun_headline_variants":["Convex points + embedding: list embeddability in P for connected graphs","Drop connectivity or embedding: list point-set embeddability NP-hard","Bi-labeled paths NP-hard on general points despite unique embedding","FPT by degree for connected graphs on convex point sets","APX-hard to maximize edges in list point-set drawings"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The claim that a purely greedy left-to-right placement of child blocks always yields a globally shortest feasible interval, with no beneficial non-greedy reordering inside a block.","fun_headline_variants_meta":{"raw":{"variants":["Convex points + embedding: list embeddability in P for connected graphs","Drop connectivity or embedding: list point-set embeddability NP-hard","Bi-labeled paths NP-hard on general points despite unique embedding","FPT by degree for connected graphs on convex point sets","APX-hard to maximize edges in list point-set drawings"]},"model":"grok-4.5","effort":"low","cost_usd":0.003863,"raw_usage":{"total_tokens":1321,"prompt_tokens":907,"num_sources_used":0,"completion_tokens":75,"cost_in_usd_ticks":38628000,"prompt_tokens_details":{"text_tokens":907,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":339,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":907,"tokens_out":75,"duration_ms":6450,"temperature":1.0,"reasoning_tokens":339,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T21:36:45.186820+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"An explicit convex instance whose shortest outerplanar realization places some earlier block non-greedily and thereby frees a strictly shorter total interval than the dynamic program reports.","supporting_citations":[],"review_version":1}