{"id":"c1eeab44-e6f5-4d60-ac92-7226af1c5114","arxiv_id":"2608.10164","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Quasi-planar graphs are exactly the iterated subdivision-cover-intersection-graphs of planar graphs.","lead":"This paper proves that a graph is quasi-isometric to a planar graph exactly when it can be built from planar graphs by repeatedly subdividing edges and taking intersection graphs of connected pieces. It provides a combinatorial handle on a geometric property, with applications to group theory.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Forward direction hinges on a sketched Lemma 6.1; missing proof of the SCIG reduction leaves Theorem 1.7 conditional.","rationale":"The reader's weakest_assumption focused on the backward direction's reliance on Davies' theorem and the missing countable qualifier, but the reader's rationale also noted that 'Lemma 6.1 is only sketched and is load-bearing for the forward implication.' I agree with that secondary observation and elevate it to the primary concern: the forward direction of the central characterization (Theorem 1.7) is not fully established because Lemma 6.1, which reduces arbitrary quasi-isometries to bi-Lipschitz equivalence with a bounded-diameter SCIG presentation, is asserted rather than proved. The proof sketch is plausible—merging stars of a shallow contraction and adding singleton sets for clique attachments are natural ideas—but the paper provides no explicit verification that the resulting cover-intersection graph matches the target graph exactly, without spurious edges, and with uniformly bounded set diameters. Without this lemma, Theorem 1.8(i)⇒(ii) has a gap, and Theorem 1.7's forward direction collapses to the weaker statement that quasi-planar graphs are iterated edge-sliding twins of planar graphs, which is not the claimed SCIG characterization. The backward direction and the other corollaries appear sound, and the detailed Lemmas 6.9 and 6.10 are credible, so the appropriate verdict remains CONDITIONAL pending a complete proof of Lemma 6.1. My recommendation does not change the reader's verdict.","tokens_in":25309,"tokens_out":25208,"duration_ms":231270,"concrete_test":"Fully write out the proof of Lemma 6.1 for the following concrete pair: let G be a path of length N, and let H be obtained from G by contracting every third edge and then attaching a triangle to each vertex of the contracted graph. Verify explicitly that H is isomorphic to the cover-intersection-graph of a subdivision of G obtained by subdividing each edge of G into at most 3 edges, with the cover consisting of the merged star sets and singleton clique sets as suggested. In particular, check that every cover set is connected and has diameter at most D(M,A) for a uniform D, that each edge of the contracted minor and each clique edge corresponds to an intersection, and that no unintended intersections occur. If the construction cannot be written down or fails on this example, Lemma 6.1 is false; if it succeeds, the forward direction still needs a general proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 6.1 claims that for any (M,A)-quasi-isometric graphs G,H, H is bi-Lipschitz equivalent to a cover-intersection-graph of a subdivision of G whose cover sets have diameter bounded in terms of M,A. This is the first step in the forward direction of Theorem 1.8, which in turn implies the forward direction of Theorem 1.7. The proof (Section 6, first paragraph) is a sketch: it cites Propositions 5.1 and 5.2 to reduce to a shallow contraction minor of G with cliques attached, then asserts without construction that these operations 'can be realized' by merging star sets and adding singleton sets in a subdivision of G. It does not specify which edges are subdivided, how the merged sets are defined when a contracted component is not a star, why the resulting intersection graph is exactly the desired graph (no missing or spurious edges), or why every cover set remains connected with diameter bounded by a function of M,A only. Since Theorem 1.8(i)⇒(ii) and thus Theorem 1.7's forward implication rely entirely on this lemma, the central characterization is not fully proved as written. The subsequent lemmas (6.9, 6.10) are detailed, but they only operate after this reduction; the hinge is unproven.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops tools in coarse graph theory around cover-intersection graphs and a new 'edge-sliding' equivalence relation, and uses them to prove a combinatorial characterization of quasi-planar graphs. Theorem 1.7 states that a graph is quasi-isometric to a planar graph if and only if it is an iterated subdivision-cover-intersection-graph (SCIG) of a planar graph. The backward direction builds on Davies' theorem that countable string graphs are quasi-planar; the forward direction is derived from the more general Theorem 1.8, which asserts that two graphs are quasi-isometric if and only if each can be obtained from the other by a bounded number of bounded-diameter SCIG operations. The paper also proves that quasi-planarity is preserved under contraction minors (Theorem 1.2), gives a tree-decomposition gluing theorem (Theorem 1.10/4.3), and derives applications to finitely generated groups, including a quasi-isometry statement for finite-index subgroups. The main technical work is in Section 6, where Lemma 6.1 reduces quasi-isometry to bi-Lipschitz equivalence, Lemma 6.9 connects bi-Lipschitz equivalence to iterated edge-sliding twins, and Lemma 6.10 performs a four-step construction realizing each edge-sliding step by two SCIG operations.","tokens_in":25490,"tokens_out":15772,"duration_ms":148935,"significance":"If the proofs are completed as intended, this is a substantial contribution: it gives a purely combinatorial, generative description of a whole quasi-isometry class, with explicit quantitative versions for families of finite graphs. The paper is careful with constants and constructive bounds, and the edge-sliding notion is likely to be of independent interest. The contraction-minor closure, the tree-decomposition theorem, and the group-theoretic corollaries are concrete, falsifiable consequences that go beyond the main characterization. However, the forward direction of the central theorem currently rests on a lemma whose proof is only sketched, so the main characterization is conditional on additional work.","major_comments":[{"comment":"The proof of Lemma 6.1 is only a sketch, and it is load-bearing: the forward direction of Theorem 1.8, and hence the forward direction of Theorem 1.7, begins with this reduction. The text says the required cover is 'natural' and that edge contractions and clique attachments 'can be realized' by merging and adding cover sets in a subdivision of G, but it does not specify which edges of G are subdivided, how the merged cover sets are defined when a contracted component from Proposition 5.2 is not a star, why the resulting intersection graph has exactly the edge set of the target graph (no missing or spurious edges), and why every cover set remains connected with diameter bounded by a function of M and A only. Without these details the claimed reduction is not checkable. I recommend proving this lemma in full, or replacing the forward direction with a direct construction.","section":"§6, Lemma 6.1"}],"minor_comments":[{"comment":"In the lower-bound estimate for d_G(x,y), the printed constant '2AM^2 r' should be '2M^2 r': the preceding inequality gives d_G(˚x_i,˚x_{i+1}) ≤ 2M^2 r + 6AM, without an extra factor of A. As written, the bound fails when A = 0.","section":"§4, proof of Theorem 4.3"},{"comment":"Section 2 states that all graphs are assumed countable, and the abstract says the results apply to infinite graphs and to finite families with uniform constants, but the statements of Theorem 1.7 and Corollary 1.6 omit the word 'countable' for infinite graphs. This qualifier should appear in the theorem statements.","section":"§2 and abstract"},{"comment":"The phrase 'by Lemma 6.1, we have reduced to the case where G and H are bi-Lipschitz equivalent' should be made explicit, since Theorem 1.8(ii) requires both memberships G ∈ SCIG_n(H) and H ∈ SCIG_n(G); the reduction uses Lemma 6.1 once in each direction. As written, the proof only describes one application.","section":"§6.2, proof of Theorem 1.8"},{"comment":"The assignment of green labels to edges of E(G2)\\E(A) is said to 'involve a choice' for edges of the second type. Please add a sentence explaining explicitly why the truth of (13) and the final isomorphism G4 ≅ H are independent of these choices; the current text asserts this but does not justify it.","section":"§6.3, proof of Lemma 6.10, Step 2"},{"comment":"The proof of (i)⇒(ii) in Lemma 6.9 begins 'suppose G and H are bi-Lipschitz equivalent via the identity map'. For a general bi-Lipschitz equivalence one should first identify the vertex sets by the given bijection; this is standard but should be stated.","section":"§6.1, Lemma 6.9"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is an appealing statement and the overall architecture is coherent, but the central forward direction is conditioned on a sketched lemma (Lemma 6.1). This is fixable within the scope of the paper, but it is not a purely cosmetic issue. The dependence on Davies' theorem for the backward direction is external and acceptable, but it should be stated as clearly as possible. The paper fits the journal's scope well."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Paul — this is a serious paper and the main result is genuinely new: quasi-planar graphs are exactly the iterated subdivision-cover-intersection-graphs of planar graphs (Thm 1.7). It also proves contraction-minor closure (Thm 1.2), which was conjectured, and a tree-decomposition preservation theorem (Thm 1.10). The machinery — Voronoi cells, edge-sliding, the local-to-global glueing in Thm 4.3 — is well-chosen, and the authors are careful with explicit constants and constructive proofs. The edge-sliding notion in Section 6.1 is a nice independent tool; Lemma 6.9 (bi-Lipschitz iff iterated edge-sliding twins) cleanly packages the metric/combinatorial interface.\n\nThe soft spots are real but not fatal. Lemma 6.1, which reduces quasi-isometric graphs to bi-Lipschitz equivalence via one SCIG operation, is the hinge of the forward direction and its proof is a sketch: 'the required cover is natural' is doing a lot of work. A referee should ask for a full construction, especially for how merged star sets produce exactly the desired intersection graph without spurious edges, and how the bounded-diameter condition is maintained when contracted components are not stars. I suspect it is fillable, but as written it is a gap in the proof of the main theorem. Similarly, the countable assumption is stated in Section 2 but omitted from the abstract and Theorem 1.7, so the 'infinite graphs' claim overreaches. There's also a small constant typo in Theorem 4.3 (2AM^2r should presumably be 2M^2r + 6AM).\n\nThe dependence on Davies' theorem for the backward direction is clearly acknowledged and is not a flaw; the reverse implication is new. No circularity or data-fitting issues.\n\nIf I were the editor, I would send this to a serious referee. The main theorem is important enough, and the rest of the paper is detailed enough, that the missing Lemma 6.1 details are worth one revise-and-resubmit cycle rather than a desk reject. The paper is for researchers in coarse graph theory, geometric group theory, and graph minors. I'd bring it to a reading group.","headline":"Strong, significant paper with a load-bearing lemma that is only sketched; the characterization is plausible and worth referee time.","tokens_in":26066,"tokens_out":2712,"would_cite":true,"duration_ms":24929,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","05C12","51F30","05C63","05C76"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph that is quasi-isometric to a planar graph is obtained from planar graphs by finitely many bounded subdivisions and cover-intersection operations, and conversely.","keywords":["quasi-isometry","quasi-planar","intersection graph","cover-intersection graph","string graph","contraction minor","edge-sliding","bi-Lipschitz equivalence"],"falsifier":"A countable graph that is quasi-isometric to a planar graph but is not an iterated subdivision-cover-intersection graph of any planar graph would refute Theorem 1.7. The square grid with both diagonals added to every cell is a concrete test case: it is non-planar, it is quasi-isometric to the planar grid, and the constructive proof must produce a finite SCIG derivation; if the number of iterations or the diameters of the cover sets grow without bound for larger and larger finite grids, the uniform finite-graph version fails.","tokens_in":25050,"feed_emoji":"🧩","tokens_out":13038,"duration_ms":110725,"temperature":0.7,"pith_summary":"Quasi-planar graphs are graphs that look planar from far away: each is quasi-isometric to a planar graph, so distances are preserved up to multiplicative and additive error. The paper's main theorem gives a purely combinatorial description of this coarse-geometric class: a graph is quasi-planar exactly when it can be obtained from a planar graph by repeating two local operations, subdividing every edge into a bounded-length path and forming the intersection graph of a family of connected subgraphs that cover the graph. The backward direction uses the known theorem that every string graph is quasi-isometric to a planar graph with universal constants, while the forward direction is new and runs through a graph operation the paper calls edge-sliding. If correct, the result means quasi-planarity is no longer only a metric notion: it is the closure of planar graphs under an explicit finite recipe.","feed_headline":"Quasi-planar graphs are built from planar graphs by two moves","feed_subtitle":"Every graph that looks planar from far away has a finite combinatorial recipe from planar graphs.","key_machinery":"The two load-bearing constructions are the subdivision-cover-intersection operation and edge-sliding. The subdivision-cover-intersection operation takes a graph, subdivides each edge into a path of length at most 3, and then forms the cover-intersection graph: the vertices are a family of connected subgraphs that cover the base graph, and two vertices are adjacent when the corresponding subgraphs intersect. Edge-sliding is an equivalence relation on graphs sharing a vertex set: an edge can be moved by sliding one endpoint along another edge of the shared frame, and two graphs are edge-sliding twins when every difference can be removed this way; twins are 2-bi-Lipschitz equivalent, and every bi-Lipschitz equivalence between graphs on the same vertex set can be decomposed into finitely many edge-slidings. The proof's core lemma realizes a single edge-sliding by two subdivision-cover-intersection operations with cover sets of diameter at most 4, while bounded-diameter cover sets make the operation quasi-isometry-preserving (Corollary 3.3).","core_discovery":"The central claim is Theorem 1.7: a graph is quasi-isometric to a planar graph if and only if it is an iterated subdivision-cover-intersection-graph of a planar graph. Iterating means starting with a planar graph and, a finite number of times, first subdividing every edge into a path of length at most 3 and then taking the intersection graph of a family of connected subgraphs whose union is the whole graph. The paper also proves the more general Theorem 1.8, in which two graphs are quasi-isometric exactly when each is obtained from the other by such operations with cover sets of bounded diameter. The backward direction of Theorem 1.7 builds on the cited theorem that every string graph is quasi-isometric to a planar graph with universal constants; the forward direction is proved by introducing edge-sliding and showing that every bi-Lipschitz equivalence decomposes into edge-slidings, each of which is realized by two subdivision-cover-intersection steps. Along the way the paper shows that contraction minors of quasi-planar graphs are quasi-planar, and that tree-decompositions with bounded-diameter adhesions and quasi-planar induced bags preserve quasi-planarity.","pith_inferences":["Inference: If the string-graph theorem is extended from planar graphs to every minor-closed family, as the paper reports is plausible, the same SCIG characterization would give a uniform combinatorial description of every quasi-minor-closed class.","Inference: The characterization turns quasi-planarity into an existence problem with finite witnesses; for fixed constants, verifying a candidate SCIG derivation is a local combinatorial check, which may make quasi-planarity algorithmically recognizable in ways that the metric definition does not.","Inference: The paper leaves open whether subdivisions can be dropped from the characterization (Problem 7.1); a positive answer would reduce the description to iterated string graphs, making the generative recipe purely intersection-theoretic."],"forward_implications":["Quasi-planarity now has a finite combinatorial certificate: a graph is quasi-planar exactly when a finite sequence of bounded subdivisions and cover-intersection steps leads from a planar graph to it.","Every contraction minor of a quasi-planar graph is quasi-planar, with constants depending explicitly on the original quasi-isometry constants.","Tree-decompositions with bounded-diameter adhesions and quasi-planar induced bags produce quasi-planar graphs, so quasi-planarity composes along tree-like splittings.","A finitely generated group that splits over a finite subgroup into virtually-planar factors is itself virtually-planar.","Any graph quasi-isometric to a planar graph is bi-Lipschitz equivalent to a planar graph, so the metric and bi-Lipschitz notions of quasi-planarity coincide at the level of existence."],"supporting_citations":[{"why":"Supplies the theorem that every countable string graph is quasi-isometric to a planar graph with universal constants, which drives the backward direction of Theorem 1.7.","marker":"[16]"},{"why":"Supplies the independent proof of the same string-graph result for finite graphs, used when the paper treats families of finite graphs with uniform constants.","marker":"[14]"},{"why":"Gives the method for making a quasi-isometry injective by attaching leaves, used to upgrade quasi-isometries to bi-Lipschitz equivalences in the forward direction.","marker":"[25, Observation 2.2]"},{"why":"Provides the lemma that radius-enlarged bags still form a tree-decomposition with controlled adhesion diameters, used in the proof of the tree-decomposition theorem.","marker":"[2, Lemma 3.3]"},{"why":"Provides the standard separation property of tree-decompositions used to locate endpoints of paths inside adhesion sets in Lemma 4.1.","marker":"[30, Theorem 10.13]"},{"why":"Supplies the separation fact used to show that radius-enlarged adhesion sets coincide with enlarged bag intersections.","marker":"[20, Lemma 12.3.1]"},{"why":"Supplies the criterion that a finitely generated group is quasi-planar exactly when it is virtually planar, converting the tree-decomposition theorem into a group-theoretic corollary.","marker":"[36, Corollary D]"}],"fun_headline_variants":["Planar look-alikes have a finite recipe: subdivide and intersect","Quasi-planar = iterated edge-subdivision and intersection graphs","New characterization: quasi-planar graphs from planar via two operations","Subdivide and intersect: the recipe for quasi-planarity","From planar to quasi-planar: subdivide and intersect"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the cited theorem, not reproved here, that every countable string graph is quasi-isometric to a planar graph with universal constants; the backward half of the main equivalence collapses if that theorem fails. The paper also assumes throughout that all graphs are countable.","fun_headline_variants_meta":{"raw":{"variants":["Planar look-alikes have a finite recipe: subdivide and intersect","Quasi-planar = iterated edge-subdivision and intersection graphs","New characterization: quasi-planar graphs from planar via two operations","Subdivide and intersect: the recipe for quasi-planarity","From planar to quasi-planar: subdivide and intersect"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000574,"raw_usage":{"total_tokens":2731,"prompt_tokens":988,"completion_tokens":1743,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":1656}},"tokens_in":604,"tokens_out":1743,"duration_ms":12626,"temperature":1.0,"reasoning_tokens":1656,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:11:18.959145+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A countable graph that is quasi-isometric to a planar graph but is not an iterated subdivision-cover-intersection graph of any planar graph would refute Theorem 1.7. The square grid with both diagonals added to every cell is a concrete test case: it is non-planar, it is quasi-isometric to the planar grid, and the constructive proof must produce a finite SCIG derivation; if the number of iterations or the diameters of the cover sets grow without bound for larger and larger finite grids, the uniform finite-graph version fails.","supporting_citations":[],"review_version":1}