{"id":"eb97d909-5e2a-41cb-aac7-6a3346a060ae","arxiv_id":"2506.12424","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Map graphs, hyperbolic uniform disk graphs, and spherical uniform disk graphs are shown to have bounded or radius-dependent layered tree-independence number, yielding new weighted subexponential algorithms.","lead":"This paper proves new bounds on the layered tree-independence number of several families of geometric intersection graphs, including map graphs, hyperbolic and spherical uniform disk graphs. The results imply new subexponential and quasi-polynomial algorithms for weighted problems such as maximum weight independent set on those graph families.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: central theorems appear correct; only minor proof slips (recoverable) and an input-representation caveat.","rationale":"The reader's condition on Theorem 3.12 is reasonable but, on inspection, the cited geometric lemma is correct and the 'parallel lines' sentence, while wrong, is not needed: the stated interval for b(s) already forces the projection s to lie between the two perpendiculars, giving c ∈ R'. The additional spherical area gap I found is a genuine proof omission for r > π/4, but it is repaired by a one-line case split using the whole-sphere area, so it does not threaten Theorem 3.15. The input-representation caveat for g-map graphs is a clarity issue rather than a correctness issue, since the structural bounds are unconditional and the algorithmic statements already carry a witness assumption in the proof. Because the central claims survive scrutiny and the needed fixes are local, the reader's CONDITIONAL verdict remains appropriate.","tokens_in":37568,"tokens_out":36079,"duration_ms":416393,"concrete_test":"Verify the geometric core of Theorem 3.12 independently: in the hyperboloid model, take ℓ as a geodesic and place points s0 and s1 on ℓ at hyperbolic distance tanh r apart, then place c0 and c1 on the perpendiculars through s0 and s1 at distance r from ℓ; compute the six pairwise hyperbolic distances for a dense grid of r values (e.g., r in 10^{-4} to 10^4) and confirm each is at most 2r. This directly checks [8, Lemma 8] as used in the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reviewing the proof of the central claims, I do not find a load-bearing flaw. The weakest point identified by the reader is the reliance of Theorem 3.12 on [8, Lemma 8] (a Saccheri quadrilateral with base tanh r and legs r has diameter at most 2r). This lemma is true: in the hyperboloid model, writing t = tanh r, the summit distance satisfies cosh d_s = cosh^2 r cosh t - sinh^2 r ≤ cosh(2r), and the diagonals satisfy cosh d_d = cosh r cosh t ≤ cosh(2r), so every vertex-to-vertex distance is < 2r; convexity then gives the bound for the whole region. The erroneous sentence in the proof of (11) ('no two parallel lines intersect') is a slip: the perpendicular through c meets ℓ at s, and the established bound (2j-3)r ≤ b(s) < 2jr, together with 2jr - h tanh r ≤ (2j-3)r, places s between ℓ0 and ℓh, so c lies in R'. A second, newly noticed gap is in Theorem 3.15: the area ratio (1-cos 4r)/(1-cos r) is only the number of disjoint caps when 4r ≤ π. For 4r > π the containing set is the whole sphere; using area(S^2) gives at most 2/(1-cos r) < 16 for r ≥ π/4, so the bound 15 still holds with a short case split. The input-representation caveat for g-map graphs (footnote 9) is a real but mild convention issue: the algorithmic statements should state that a witness or embedding is provided.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies layered tree-independence number, clique cover degeneracy, independence degeneracy, and clique-based separators for geometric intersection graphs. Its central structural contributions are: O(g) layered tree-independence number for g-map graphs (Corollary 3.6), O(r/tanh r) for hyperbolic uniform disk graphs of radius r (Theorem 3.12), O(1) for spherical uniform disk graphs (Theorem 3.15), and bounded layered tree-independence number for powers of bounded layered-treewidth graphs. Section 4 bounds clique cover degeneracy for 0-map graphs, spherical disk graphs, and contact string graphs; Section 5 combines these bounds to produce sublinear-weight clique-based separators; Section 6 proves that every fractionally tree-α-fragile class is polynomially (dgn,ω)-bounded and formulates Conjecture 1.4. Algorithmic corollaries for weighted Max Weight Independent Set, Min Weight Feedback Vertex Set, and related problems are derived from these bounds.","tokens_in":37888,"tokens_out":23120,"duration_ms":290459,"significance":"If the results stand, they give strong positive evidence for Question 1.2 on several important classes and extend subexponential-time weighted algorithms to geometric graphs where only unweighted algorithms were previously known. The r-neighborhood cliquification operation (Theorem 3.1) is a clean and reusable tool. The paper is careful about explicit constants and about separating structural from algorithmic statements; the main proofs are mostly self-contained, with only standard geometric facts imported from [8]. The two proof gaps I found are local and repairable, and I do not see a threat to the central claims.","major_comments":[{"comment":"The proof as written contains an invalid geometric justification. The sentence 'if c ∉ R′, then the line through c perpendicular to ℓ... must intersect one of ℓ0 and ℓh, contradicting the fact that no two parallel lines intersect' is not a valid argument: a line perpendicular to ℓ at a point beyond s0 or before sh is simply another disjoint perpendicular, not a line crossing ℓ0 or ℓh. Moreover, the claimed strict inequality b(s) < 2jr can fail when the center c lies on the ray Si at distance exactly 2jr, since Rj is defined with a closed upper endpoint. The intended conclusion is recoverable: the correct bound is (2j−3)r ≤ b(s) ≤ 2jr, and since h tanh r ≥ 3r, the foot s lies between s0 and sh; together with d(c,ℓ) ≤ r this places c in R′. The proof should be repaired by replacing the strict inequality with a non-strict one and by deleting or correcting the parallel-lines sentence.","section":"Theorem 3.12, proof of (11)"},{"comment":"The areal argument bounding the number of pairwise non-intersecting disks by (1−cos 4r)/(1−cos r) is only valid when 4r ≤ π. If 4r > π, the 'disk of radius 4r' centered at z is the whole sphere, whose area is 4π, not 2π(1−cos 4r). This case is not handled in the manuscript. The bound 15 is still correct: for r ≥ π/4, the area of S2 gives at most 4π/(2π(1−cos r)) = 2/(1−cos r) < 16, so the final 15+15=30 estimate survives. The proof should be split into the cases 4r ≤ π and 4r > π, or an equivalent argument should be provided.","section":"Theorem 3.15, proof of (13)–(14)"},{"comment":"The proof chooses z = ((2j−1)r, zi) on the ray Si. This is legitimate only when (2j−1)r ≤ π, and the manuscript does not state why this holds. The missing justification is that if (2j−1)r > π, then every center c with b(c) > (2j−2)r satisfies π − b(c) < r, so the disk centered at c contains the antipode o∗ and therefore intersects the polar axis ℓ; such a vertex belongs to U, not U′. Thus for a vertex in Xti ∩ Vj ∩ U′, the quantity (2j−1)r is indeed at most π. This is a local omission, but it should be made explicit so that the construction of z is fully justified.","section":"Theorem 3.15, proof of (13), existence of the point z"}],"minor_comments":[{"comment":"The proof invokes Theorem 3.4, which is stated for connected graphs. A witness H of a g-map graph may be disconnected; the proof should either state that H can be assumed connected without loss of generality or explain how to combine the component-wise tree decompositions and layerings.","section":"Corollary 3.6"},{"comment":"The algorithmic statements depend on the input graph being given together with a geometric realization, as noted in the preceding remarks. This convention should be moved into the theorem statements themselves, since the claimed O(n log n) computation of θ− and θ+ values is only meaningful with that input.","section":"Theorems 3.12 and 3.15"},{"comment":"In the replacement step, the sentence claiming that a Euclidean disk C of the same radius as φ(A) can be drawn inside φ(B) and tangent to φ(A) at φ(s) is terse. A one-sentence justification of why such a disk exists would improve readability and remove any ambiguity about the containment.","section":"Proposition 4.2"}],"recommendation":"major_revision","confidential_remarks":"The two proof gaps identified in Theorem 3.12 and Theorem 3.15 are local and can be repaired without changing the statements or the main algorithmic consequences. I found no issue with the correctness of the r-neighborhood cliquification machinery, the clique cover degeneracy arguments, or the separator corollaries. The paper is a good fit for math.CO and the contribution is substantial."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper resolves the spherical uniform disk graph case of the open problem from Bläsius et al., gives the first O(1) bound there, and extends layered tree-independence bounds to g-map graphs and hyperbolic uniform disk graphs with radius-dependent bounds. The r-neighborhood cliquification operation is a genuinely useful addition, and the algorithmic consequences for weighted problems follow cleanly from existing machinery. The lower-bound example for contact string graphs is also a nice separation result.\n\nI checked the central proofs with the stress-test note in hand. The main theorems hold up. The false sentence in Theorem 3.12 about parallel lines intersecting is a real slip, but it is not load-bearing: the earlier inequality (2j-3)r <= b(s) < 2jr is enough to place the center in the intended region, so the bound 6*ceil(r/tanh r) survives. The spherical proof has a quieter but equally fixable gap: the area ratio (1-cos 4r)/(1-cos r) only counts disjoint caps when 4r <= pi. For larger radii a short case split using the whole sphere area gives the same constant. Both issues are minor and recoverable.\n\nThe input-representation caveat for g-map graphs is worth fixing. The algorithmic statements should state that a witness or embedding is provided, or the algorithms should be phrased for embedded inputs. That is a convention issue, not a mathematical one.\n\nOverall this is a strong, carefully written paper with real progress on an open question. The proofs are detailed, the literature is handled honestly, and the self-citations to prior work are appropriate background rather than a circularity problem. A serious referee will find the main claims correct after minor repairs. I would send it to review.","headline":"Strong new bounds on layered tree-independence number for map graphs and non-Euclidean disk graphs; a few fixable proof slips, but the core is sound.","tokens_in":38438,"tokens_out":1098,"would_cite":true,"duration_ms":120731,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","05C75","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves bounded layered tree-independence number for g-map graphs, hyperbolic uniform disk graphs, and spherical uniform disk graphs, and combines this with bounded clique cover degeneracy to obtain clique-based separators of…","keywords":["layered tree-independence number","clique-based separators","map graphs","hyperbolic uniform disk graphs","spherical uniform disk graphs","clique cover degeneracy","tree-independence number","geometric intersection graphs"],"falsifier":"Compute the actual hyperbolic diameter of the Saccheri quadrilateral with base $\\tanh r$ and legs $r$; if for some $r$ this diameter exceeds $2r$, then two disjoint radius-$r$ disks can fit in one cell of the partition used in Theorem 3.12, and the $6\\lceil r/\\tanh r\\rceil$ bound collapses.","tokens_in":37367,"feed_emoji":"📐","tokens_out":9311,"duration_ms":94590,"temperature":0.7,"pith_summary":"This paper studies a structural question: if a graph class has bounded layered tree-independence number—a measure of how well a graph can be decomposed into a tree of bags while each bag stays small in each vertex layer—does it always have balanced separators built from disjoint cliques with sublinear total weight? The authors establish bounded layered tree-independence for g-map graphs, hyperbolic uniform disk graphs of radius r, and spherical uniform disk graphs of radius r, with explicit bounds. They then show that for these classes the structural bound combines with bounded clique cover degeneracy to produce clique-based separators of sublinear size, giving positive evidence for the open question. The same bounds lead to subexponential or quasi-polynomial algorithms for weighted problems such as Max Weight Independent Set and Min Weight Feedback Vertex Set on these geometric graph classes.","feed_headline":"Map and curved disk graphs have bounded layered tree-independence","feed_subtitle":"The bounds produce sublinear clique separators and faster weighted algorithms for these geometric graph classes.","key_machinery":"The load-bearing device is the r-neighborhood cliquification: given a graph G and a set P of vertices, add all missing edges among vertices within distance r of each p in P. For a graph with layered treewidth k, the cliquification has layered tree-independence number at most 4rk, and the proof builds the new layering by merging 2r consecutive layers and enlarging each bag along shortest paths to P. g-map graphs arise as such cliquifications of bounded-genus bipartite witnesses, and odd and even powers arise from cliquifications of pendant-edge gadgets. For hyperbolic and spherical uniform disk graphs, the proof uses a polar-coordinate model: layers are radial annuli of width 2r, bags are angular rays, and the bound on independent vertices inside a bag-layer intersection comes from a packing argument—for hyperbolic disks, subdividing each annulus into Saccheri quadrilaterals whose diameter is at most 2r; for spherical disks, an area-ratio estimate showing at most 15 disjoint disks can sit in each half of a bag-layer intersection. Finally, bounded clique cover degeneracy supplies the linear θ-binding function f(x)=kx that converts a balanced bag of independence number O(√n) into a clique-based separator of sublinear weight.","core_discovery":"The paper's central discovery is that bounded layered tree-independence number, although not known to imply sublinear clique-based separators in general, does imply them once bounded clique cover degeneracy is added. Concretely, Corollary 3.6 gives a polynomial-time computable tree decomposition and layering of any g-map graph witnessing layered tree-independence number at most 6g+9; Theorem 3.12 gives 6⌈r/tanh r⌉ for hyperbolic uniform disk graphs of radius r; Theorem 3.15 gives the radius-independent bound 30 for spherical uniform disk graphs. Section 4 bounds clique cover degeneracy by 3 for 0-map graphs, by 6 for spherical uniform disk graphs, and by 4 for contact string graphs. Combining these, Corollary 5.3 yields clique-based separators of size O(√n) for 0-map graphs and unit disk graphs, O(√(r/tanh r)·√n) for hyperbolic uniform disk graphs, and O(√n) for spherical uniform disk graphs. The same machinery also shows that powers of bounded layered treewidth graphs have bounded layered tree-independence number, and that contact segment graphs have unbounded layered tree-independence number, so contact string graphs are not all 0-map graphs.","pith_inferences":["Beyond the paper, the same recipe—bounded layered tree-independence number plus bounded clique cover degeneracy implies sublinear clique-based separators—could be tested on other geometric intersection classes where one bound is known but the other is not yet established.","The separation between contact segment graphs and 0-map graphs suggests a finer hierarchy: one-sided contact string graphs sit inside 0-map graphs, while general contact string graphs do not, so probing which intermediate contact classes inherit bounded layered tree-independence would be a natural next step.","If the Saccheri-quadrilateral diameter bound ever failed, the hyperbolic theorem as stated would need repair, but the spherical and map-graph results would remain intact, so the overall positive evidence for Question 1.2 would not be threatened.","Resolving Question 7.1 affirmatively would improve the hyperbolic layered tree-independence bound to a constant, which by the paper's Lemma 6.1 would also give bounded independence degeneracy for hyperbolic uniform disk graphs."],"forward_implications":["Every n-vertex g-map graph, spherical uniform disk graph, and unit disk graph admits a clique-based separator of size O(√n) that can be computed in polynomial time from a suitable realization.","Hyperbolic uniform disk graphs of radius r admit clique-based separators of size O(√(r/tanh r)·√n), interpolating between the Euclidean-like regime of bounded r and the firmly hyperbolic regime of large r.","Max Weight Independent Set and Min Weight Feedback Vertex Set, and more generally Max Weight Distance-d Packing for even d, have 2^{O(√n log n)}-time algorithms on g-map graphs and spherical uniform disk graphs, and quasi-polynomial-time algorithms on hyperbolic uniform disk graphs when r is not too small.","Powers of bounded layered treewidth graphs have bounded layered tree-independence number, so the separator and algorithmic consequences apply to those powers as well.","Contact segment graphs have unbounded local tree-independence number, while contact string graphs still have clique cover degeneracy at most 4 and hence chromatic number at most 4 times the clique number."],"supporting_citations":[{"why":"Defines layered tree-independence number, poses Question 1.2, and proves Lemma 2.2 converting layered tree-α to tree-α.","marker":"[32]"},{"why":"Supplies the Saccheri-quadrilateral diameter lemma, the clique cover degeneracy bound for hyperbolic uniform disk graphs, and earlier separator algorithms this paper improves.","marker":"[8]"},{"why":"Establishes the clique-based-separator framework and the 2^{O(w(n))}-time algorithms for Independent Set and Feedback Vertex Set used in the algorithmic corollaries.","marker":"[22]"},{"why":"Gives clique-based separators for Euclidean disk graphs and the ETH-tight algorithm framework, providing the O(√n) separators for disk and unit disk graphs.","marker":"[21]"},{"why":"Introduces layered treewidth and layered separators and proves the bounded-genus BFS layering theorem that seeds the map-graph bounds.","marker":"[27]"},{"why":"Characterizes g-map graphs as half-squares of bounded-genus bipartite witnesses, which Corollary 3.6 uses.","marker":"[26]"},{"why":"Provides Lemma 2.1 connecting tree-independence number to treewidth via Ramsey numbers and the lemma used for independence degeneracy from bounded layered tree-α.","marker":"[19]"},{"why":"Gives the tree-independence-parameterized algorithms for Max Weight Distance-d Packing and Min Weight Feedback Vertex Set invoked in Corollary 1.5.","marker":"[43]"},{"why":"Shows planar graphs have clique cover degeneracy at most 3, the base case extended to 0-map graphs in Proposition 4.1.","marker":"[55]"}],"fun_headline_variants":["Map and curved disk graphs have bounded tree-independence","Bounded tree-independence for map, hyperbolic, and spherical disk graphs","Sublinear clique separators for map and disk graphs","Tree-independence bounds for map and disk graph classes","Faster weighted algorithms on map and disk graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hyperbolic radius bound rests on a cited geometric lemma saying each Saccheri quadrilateral of base $\\tanh r$ and legs $r$ has diameter at most $2r$; the whole packing argument for that theorem depends on this one estimate.","fun_headline_variants_meta":{"raw":{"variants":["Map and curved disk graphs have bounded tree-independence","Bounded tree-independence for map, hyperbolic, and spherical disk graphs","Sublinear clique separators for map and disk graphs","Tree-independence bounds for map and disk graph classes","Faster weighted algorithms on map and disk graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001698,"raw_usage":{"total_tokens":6751,"prompt_tokens":998,"completion_tokens":5753,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":5674}},"tokens_in":614,"tokens_out":5753,"duration_ms":55384,"temperature":1.0,"reasoning_tokens":5674,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:53:21.464810+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the actual hyperbolic diameter of the Saccheri quadrilateral with base $\\tanh r$ and legs $r$; if for some $r$ this diameter exceeds $2r$, then two disjoint radius-$r$ disks can fit in one cell of the partition used in Theorem 3.12, and the $6\\lceil r/\\tanh r\\rceil$ bound collapses.","supporting_citations":[{"cited_title":"Structure and Independence in Hyperbolic Uniform Disk Graphs","cited_arxiv_id":"2407.09362","evidence_quote":"Supplies the Saccheri-quadrilateral diameter lemma, the clique cover degeneracy bound for hyperbolic uniform disk graphs, and earlier separator algorithms this paper improves."},{"cited_title":"Clique- based separators for geometric intersection graphs.Algorithmica, 85(6):1652–1678, 2023","cited_arxiv_id":null,"evidence_quote":"Establishes the clique-based-separator framework and the 2^{O(w(n))}-time algorithms for Independent Set and Feedback Vertex Set used in the algorithmic corollaries."},{"cited_title":"Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C","cited_arxiv_id":null,"evidence_quote":"Gives clique-based separators for Euclidean disk graphs and the ETH-tight algorithm framework, providing the O(√n) separators for disk and unit disk graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Characterizes g-map graphs as half-squares of bounded-genus bipartite witnesses, which Corollary 3.6 uses."},{"cited_title":"Treewidth versus clique number","cited_arxiv_id":null,"evidence_quote":"Provides Lemma 2.1 connecting tree-independence number to treewidth via Ramsey numbers and the lemma used for independence degeneracy from bounded layered tree-α."},{"cited_title":"Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel","cited_arxiv_id":null,"evidence_quote":"Gives the tree-independence-parameterized algorithms for Max Weight Distance-d Packing and Min Weight Feedback Vertex Set invoked in Corollary 1.5."},{"cited_title":"Elimination graphs","cited_arxiv_id":null,"evidence_quote":"Shows planar graphs have clique cover degeneracy at most 3, the base case extended to 0-map graphs in Proposition 4.1."}],"review_version":1}