{"id":"8bc7555d-eaf3-4437-b0fe-650e7997af7b","arxiv_id":"2608.05508","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A concrete tripod-decomposition counterexample shows that Claim 2 in the 42-queue layout paper of Bekos, Gronemann, and Raftopoulou is false, so the 42 bound is not proved.","lead":"This short note exhibits a 19-vertex planar triangulation where a key 'missed path' property used by Bekos, Gronemann, and Raftopoulou's 42-queue layout proof fails, so their published argument does not establish the 42-queue upper bound for planar graphs. A generalist reader may care because it corrects the literature on a long-standing open problem in graph layout and leaves the best published bound at 48 queues.","discovery_kind":"replication","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The gap rests on an unverified execution of BGR's unspecified augmentation and base-edge choices; without confirmation that {τ6, τ7, d} can be a Q2/Q3 component under BGR's actual rules, the counterexample may not be legal.","rationale":"The reader's weakest assumption—that BGR leaves the subdivision and base-edge choices unspecified, and that the Figure 2 geometry is read correctly—is exactly the load-bearing point. The note's counterexample is convincing only if the constructed H' and the Q2/Q3 labeling of c are reachable under BGR's published algorithm. The note asserts these freedoms but does not prove them from the text of [4]; it also relies on a drawing rather than a formal certificate for the tripod geometry. These are not internal contradictions, but they are unverified dependencies. The reader accepted with moderate confidence; I agree with that assessment but believe the appropriate verdict is conditional acceptance: the gap is established only after confirming that the chosen execution is legal under BGR's rules. If the check fails, the note's central claim collapses; if it passes, the gap stands and the published 42-queue proof is indeed incomplete. The concrete test above would settle this directly.","tokens_in":6793,"tokens_out":12340,"duration_ms":108281,"concrete_test":"Inspect the published text of [4] (Algorithmica 2023) to extract the exact augmentation step, including the drawing-preserving completion of [3,15], and the base-edge rule used for the 5-queue layout. Then implement those rules on the 19-vertex graph of Figure 2 with explicit coordinates and embedding, and enumerate all choices the text leaves open. If every legal execution either separates τ6 and τ7 into different next-level components or assigns c={τ6, τ7, d} only to Q4, then Claim 2 may survive and the note's gap is not established; if some legal execution yields c as a Q2/Q3 component with T(c) touching all three paths of τ4, the gap lands.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The note's central claim is that Claim 2 is false in a BGR-valid instance. Its proof depends on three unverified freedoms: (i) which of the parallel edges between τ3 and τ4 is subdivided by d; (ii) which edges the drawing-preserving augmentation [3,15] adds; and (iii) which queue (Q2, Q3, or Q4) the single component c={τ6, τ7, d} receives in the 5-queue layout. The note asserts that BGR 'does not prescribe' these choices, but it does not reproduce the exact rules in [4] or show that all legal executions include the required one. If the augmentation in [4] is canonical—e.g., it always subdivides the edge that keeps τ6 and τ7 in different faces—or if the base-edge rule fixes c to Q4, then T(c) never needs to satisfy Claim 2 in the proof of Lemma 6, and the gap evaporates. The geometric fact that V(τ6) misses p1_4 while V(τ7) misses p2_4 is read from Figure 2; no coordinate list or machine-checked certificate is supplied. Thus the counterexample is conditional on an admissibility assumption that is not discharged within the note itself.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The note argues that the proof of the 42-queue upper bound for planar graphs by Bekos, Gronemann, and Raftopoulou (BGR) contains a gap. It isolates an implicit claim, called Claim 2, that every next-level component's tripod-vertices miss a vertical path of the parent tripod, and constructs a 19-vertex plane triangulation with a tripod decomposition in which a next-level component c = {τ6, τ7, d} has tripod-vertices touching all three vertical paths of τ4. The note concludes that Claim 2 is false, that the proof of Lemma 6 in BGR therefore does not go through, and that the surviving bound from this approach is 48 queues.","tokens_in":7016,"tokens_out":10572,"duration_ms":84061,"significance":"If the counterexample is valid, the note correctly identifies a serious gap in a published proof, restoring 48 as the best queue-number bound obtained via the product-structure route. The argument is logically clear and carefully limited: it does not assert that planar graphs have queue number greater than 42, only that BGR's proof is incomplete. The note is honest about the surviving 48-queue bound and suggests two plausible repair directions. However, the validity of the counterexample rests on the legality of the specific H′ construction and on the claim that c can be a Q2/Q3-component; these points are asserted rather than fully demonstrated, which weakens the note in its current form.","major_comments":[{"comment":"The counterexample relies on the assertion that BGR's augmentation step leaves open which parallel edge between τ3 and τ4 is subdivided and that adding the edges (τ6,d) and (τ7,d) yields a valid maximal planar 3-tree H′. The note says BGR 'does not prescribe' these choices, but it does not reproduce the exact augmentation rule from [4] or show that the displayed H′ is a legal output of that rule. If BGR's augmentation is canonical and always separates τ6 and τ7, then the instance is not a valid execution. Please provide the precise rules from [4] and prove that the displayed H′ (or some H′ with the same component c) is among the legal outputs.","section":"§3.1, Figure 2(c)"},{"comment":"The claim that 'there are valid executions in which c is one of the Q2-components or one of the Q3-components' is essential, because Claim 2 is applied in BGR only to Q2/Q3-components. The note does not exhibit a 5-queue layout of H′ or prove that some legal base-edge choice assigns the edges from τ4 to c to Q2 or Q3. Without this, the gap may be evadable by choosing a base edge that assigns c to Q4. Please supply the explicit 5-queue layout or a rigorous argument that such a choice exists.","section":"§3.1, last paragraph"},{"comment":"The geometric facts that V(τ6) misses p1_4 and V(τ7) misses p2_4 are stated from the figure, but no coordinate list or formal description of the tripod decomposition is given. Since these facts are load-bearing for the contradiction to Claim 2, the note should make the instance machine-checkable (for example, by providing vertex coordinates, the BFS tree, and the tripod recursion in a table).","section":"§3.1, Figure 2(b)"}],"minor_comments":[{"comment":"The sentence 'The 6-queue saving for inter-bag edges proved in Lemma 6 is not established by the published proof' could be clearer if it distinguished the two savings mentioned in the abstract; the 1-queue saving for intra-bag inter-layer edges is retained.","section":"§3.2"},{"comment":"The definition of the paths p1_i, p2_i, p3_i in the sentence beginning 'For i = 1,2,3' is dense; a short reference to Figure 1(b) would help the reader.","section":"§2, paragraph on Claim 1"},{"comment":"The phrase 'one of the choices required by the algorithm is not guaranteed to exist' could be made more precise by naming the choice (the first vertical path in the tripod reordering) already in the abstract.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The note addresses a real and likely genuine gap; the author is a domain expert and the counterexample is simple. However, as a formal matter, the legal-execution issue must be closed. If the author can provide the 5-queue layout and the augmentation rule, the note would be acceptable. The note does not overclaim; it appropriately states that the 42 bound is not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this note does what it says. It points to a specific load-bearing claim in BGR's 42-queue paper, gives a 19-vertex plane triangulation where that claim fails, and explains why the failure happens: the drawing-preserving augmentation can merge tripods from different recursive regions into one next-level component, so each tripod misses a different vertical path and the union touches all three. That mechanism is new as far as I know, and it is a clean way to refute the published proof without having to produce a lower bound above 42. The note also correctly rescues the separate one-queue saving for intra-bag inter-layer edges, leaving 48 queues from the product-structure route. Credit where due: the paper is well-scoped, carefully states what it does and does not show, and the explicit elimination order certifying that H' is a maximal planar 3-tree is a nice concrete touch.\n\nThe main soft spot is the one the stress-test note flagged: the counterexample depends on BGR leaving certain choices open—which parallel edge is subdivided, how the augmentation is completed, and which queue the component c receives in the 5-queue layout. The note asserts BGR does not prescribe these choices but does not re-derive BGR's full rules. I checked the relevant passage: the note is explicit about this assumption and invites the reader to verify. For a note of this kind, that is acceptable, especially since the author is clearly an expert in the area. The geometry is presented through a figure rather than a coordinate list, but the text describes which paths are touched and missed, and the figure is clear enough for a specialist to verify. These are minor concerns, not load-bearing flaws.\n\nThe stress-test worry that the gap could \"evaporate\" if BGR's augmentation is canonical is not supported by the paper under review. The note's whole point is that the published proof relies on a generic drawing-preserving augmentation [3,15] and does not enforce region-preservation. Unless the BGR paper secretly has such a rule, the counterexample executes legally. I did not see evidence of such a rule in the note's summary, and the author is in a position to know.\n\nWho benefits: anyone working on queue layouts, graph product structure, or planar graph linear layouts. The note is a useful correction to the literature and would prevent future papers from citing the 42 bound as established. It deserves a serious referee—not because it is earth-shattering, but because correcting a published upper bound is important for the community and the argument is sound. I would send it to peer review and expect it to be accepted after possibly adding a bit more detail about the execution choices.\n\nRecommendation: engage with it; it is a legitimate, well-executed critique.","headline":"A short, credible note that identifies a real gap in BGR's 42-queue proof; the 19-vertex counterexample is well targeted and the paper honestly limits its claim to invalidating the published argument, not lowering the bound.","tokens_in":7565,"tokens_out":1506,"would_cite":true,"duration_ms":16307,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that the published proof of the 42-queue upper bound for planar graphs has a gap: a 19-vertex instance shows that the required missed-path property of a next-level component can fail, so the bound is not established.","keywords":["queue layout","queue number","planar graphs","tripod decomposition","product structure","planar 3-trees","proof gap","counterexample"],"falsifier":"Reproduce the BGR construction on the 19-vertex graph of Figure 2(a) with the tripod decomposition of Figure 2(b), and test every valid choice of subdivision and base edge. If every resulting next-level component of L2 adjacent to τ4 has tripod-vertices that miss some vertical path of τ4, then Claim 2 survives for this instance and the gap could be evadable.","tokens_in":6549,"feed_emoji":"🧩","tokens_out":5420,"duration_ms":41928,"temperature":0.7,"pith_summary":"This note tries to establish that the recent proof of a 42-queue upper bound for planar graphs, due to Bekos, Gronemann, and Raftopoulou, contains a genuine gap. It exhibits a concrete plane triangulation with 19 vertices and a valid execution of the algorithm in which a next-level component's tripod-vertices touch all three vertical paths of the parent tripod, contradicting a claim the proof relies on. Consequently, the published argument does not prove the 42-queue bound; the product-structure approach only yields a 48-queue bound. The author also sketches two possible repair directions, but does not establish either one.","feed_headline":"Gap found in 42-queue proof for planar graphs","feed_subtitle":"A 19-vertex counterexample shows a key claimed property fails, leaving only a 48-queue upper bound.","key_machinery":"The key object is the tripod reordering step of BGR, which orders the three vertical paths of each tripod so that a suitable next-level component misses the first path. The counterexample centers on the component c = {τ6, τ7, d}, formed after subdividing a parallel edge between τ3 and τ4 with an auxiliary vertex d and adding edges (τ6, d) and (τ7, d) to complete the partial 3-tree H0 to a maximal planar 3-tree H′. The peeling levels are L0 = {τ0, τ1, τ2}, L1 = {τ3, τ4, τ5}, and L2 = {τ6, τ7, d}; c is the L2-neighborhood of τ4, and the 5-queue layout of planar 3-trees assigns edges between τ4 and c to one of the binding queues Q2 or Q3.","core_discovery":"The central discovery is that Claim 2 in the BGR algorithm is false in general. For the 19-vertex triangulation G shown in Figure 2, the next-level component c = {τ6, τ7, d} adjacent to τ4 has tripod-vertices T(c) = V(τ6) ∪ V(τ7). Since V(τ6) misses $p^{1}$_4 and V(τ7) misses $p^{2}$_4, their union touches all three vertical paths $p^{1}$_4, $p^{2}$_4, $p^{3}$_4, so T(c) misses no vertical path of τ4. This contradicts Claim 2, which Lemma 6 applies to every Q2- and Q3-component, including c. The underlying cause is that augmenting H0 to a maximal planar 3-tree can merge tripods from different recursive regions, and the missed paths supplied by each region need not coincide.","pith_inferences":["The gap suggests that any argument relying on local missed-path properties must keep next-level components within a single recursive region; otherwise the missed paths from different regions can cancel out, leaving no missed path.","The counterexample may indicate that other queue-layout algorithms using arbitrary augmentation of partial 3-trees face similar obstructions when merging topological sectors.","A testable next step is to determine whether a constrained, region-preserving augmentation can recover the 6-queue saving, potentially yielding a bound between 42 and 48, or whether the true queue number of planar graphs is closer to the lower bound."],"forward_implications":["The published proof does not establish the 42-queue upper bound for planar graphs.","The best bound validated by the product-structure approach remains 48 queues, since the separate one-queue saving for intra-bag inter-layer edges is still valid.","The tripod reordering step of BGR cannot be applied as stated to arbitrary tripod decompositions.","Repairing the proof requires either a region-preserving augmentation of partial planar 3-trees or a 5-queue layout for embedded multigraphs."],"supporting_citations":[{"why":"The algorithm whose proof is being critiqued; its Claim 2 and tripod reordering step are the target of the counterexample.","marker":"[4]"},{"why":"The original product-structure proof that establishes the 49-queue upper bound, which BGR attempts to improve and which supplies the tripod decomposition framework.","marker":"[8]"},{"why":"The 5-queue layout algorithm for planar 3-trees that BGR applies to the augmented graph H′ and that defines the Q2 and Q3 binding queues used in the argument.","marker":"[1]"},{"why":"Provides the generic drawing-preserving augmentation of partial 3-trees used to complete H0 to a maximal planar 3-tree H′.","marker":"[3]"},{"why":"The other cited source for the augmentation step, which the paper notes does not guarantee the region-preserving property needed for Claim 2.","marker":"[15]"}],"fun_headline_variants":["19-vertex graph exposes gap in 42-queue proof","Planar queue layout bound of 42 not proven","Counterexample for planar graph queue claim","Gap in 42-queue algorithm for planar graphs","Queue layout proof flaw: 42-queue claim unsupported"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The counterexample assumes that BGR's algorithm permits the specific execution: the parallel edge between τ3 and τ4 can be subdivided as shown, the base-edge choice makes c a Q2- or Q3-component, and the geometric fact from Figure 2 that τ6 misses $p^{1}$_4 while τ7 misses $p^{2}$_4 is correct.","fun_headline_variants_meta":{"raw":{"variants":["19-vertex graph exposes gap in 42-queue proof","Planar queue layout bound of 42 not proven","Counterexample for planar graph queue claim","Gap in 42-queue algorithm for planar graphs","Queue layout proof flaw: 42-queue claim unsupported"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000429,"raw_usage":{"total_tokens":2200,"prompt_tokens":958,"completion_tokens":1242,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":1164}},"tokens_in":574,"tokens_out":1242,"duration_ms":10581,"temperature":1.0,"reasoning_tokens":1164,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:48:15.475825+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Reproduce the BGR construction on the 19-vertex graph of Figure 2(a) with the tripod decomposition of Figure 2(b), and test every valid choice of subdivision and base edge. If every resulting next-level component of L2 adjacent to τ4 has tripod-vertices that miss some vertical path of τ4, then Claim 2 survives for this instance and the gap could be evadable.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The algorithm whose proof is being critiqued; its Claim 2 and tripod reordering step are the target of the counterexample."},{"cited_title":"Dujmovi´c, G","cited_arxiv_id":null,"evidence_quote":"The original product-structure proof that establishes the 49-queue upper bound, which BGR attempts to improve and which supplies the tripod decomposition framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The 5-queue layout algorithm for planar 3-trees that BGR applies to the augmented graph H′ and that defines the Q2 and Q3 binding queues used in the argument."},{"cited_title":"Arnborg and A","cited_arxiv_id":null,"evidence_quote":"Provides the generic drawing-preserving augmentation of partial 3-trees used to complete H0 to a maximal planar 3-tree H′."},{"cited_title":"A note on planar partial 3-trees","cited_arxiv_id":"1210.8113","evidence_quote":"The other cited source for the augmentation step, which the paper notes does not guarantee the region-preserving property needed for Claim 2."}],"review_version":1}