{"id":"c796d75e-96b9-4ef6-af46-c3c5cc8468dd","arxiv_id":"2507.00252","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Semilinear and terrain-like graphs on n vertices have biclique covers of size O(n polylog n), while some unit disk graphs require Ω(n^{4/3}) size.","lead":"This paper proves that two broad classes of geometric graphs, semilinear and terrain-like graphs, can be stored compactly using biclique covers of near-linear size. It also constructs unit disk graphs that resist such compression, settling an open question about the limits of these representations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower-bound contribution is not established as written: Lemma 26's Claim 1 proof is broken, and Lemma 27's unit-disk realization of halfplane incidences lacks the error control needed to make the reduction exact.","rationale":"The reader's explicit weakest_assumption—the unproved reduction to dnf-semilinear graphs from Tomon [79]—is a citation to a published theorem and is likely correct; moreover, the rest of the proof of Theorem 8 is coherent once that reduction is granted. The genuinely load-bearing weak point is the lower-bound section. The proof of Lemma 26's Claim 1, on which the whole section depends, is not a proof: the 'leftmost incidence' dichotomy is false as stated, and no alternative argument is given. Lemma 27's unit-disk realization is also asserted rather than shown; exact modeling of halfplanes by disks requires quantitative control of curvature versus separation, and the text does not supply it. These are internal gaps, not disagreements with consensus. The upper-bound results (Theorems 6, 8, 13, 16, 17, 22, 24) are supported by derivations and appear sound; the terrain-like and semilinear upper bounds are not affected. Thus the correct disposition remains CONDITIONAL: the lower-bound claims need either a completed proof of Claim 1 and the disk reduction, or replacement by a different lower-bound construction, before the paper's advertised negative answer to Toth's question is established.","tokens_in":22163,"tokens_out":43063,"duration_ms":567406,"concrete_test":"1) Complete the induction for Claim 1: for Pi in the intersection of the closed lower halfplanes of Li, let p be the leftmost point of Pi and show either deg(p)=1 or some line incident to p has degree 1; if this fails, find a configuration with ι>|P|+|L|, e.g., by exhaustive search over small line arrangements. 2) For Lemma 27, write the reduction explicitly: with D = diam(P) and η = min distance from a non-incident point-line pair, choose δ<η/2 and R>D^2/δ, place a circle of radius R tangent to each shifted line below it, scale by 2/R, and verify for every point-line pair that p is inside the scaled disk iff p lies in the shifted lower halfplane. A high-precision run on the standard Erdos ST construction would reveal any boundary mismatch.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 6's lower-bound proof is the load-bearing gap. Lemma 26, Claim 1 asserts ι(Pi,Li) ≤ |Pi|+|Li| whenever Pi lies in the intersection of the closed lower halfplanes bounded by Li. The proof says: 'Consider the leftmost incidence... Suppose p is incident to more than one line. It must then be the case that ℓ does not contain any other point than p.' The claimed dichotomy is false as stated: take lines y=0 and y=x with P={(0,0),(1,0)}; p=(0,0) is on both lines, and y=0 contains another point, yet all points lie in both lower halfplanes. The intended induction, presumably from Erickson [43], is not supplied, so the Ω(n^{4/3}) bound for point-halfplane incidence graphs is unsupported. Lemma 27 then asserts that this incidence graph can be realized exactly by unit disks, but a unit disk tangent to a line only contains points below a parabola y < -x^2/4; exact realization needs a quantitative bound of the form R ≳ D^2/δ for the global spread D and minimum separation δ, and the proof gives no construction or estimates. The negative answer to Toth's question therefore rests on two unproved steps.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies biclique covers of graphs, where size is the sum of the vertex counts of the bicliques. It surveys classical and recent results and contributes new upper bounds: semilinear graphs of constant complexity admit biclique covers of size O(n polylog n), terrain-like (capped) graphs admit partitions of size O(n log^3 n), and several restricted classes (grounded L-shapes, x-grounded L-shapes, grid graphs, interval graphs, bounded-boxicity graphs, bichromatic segment intersection graphs) receive improved or matching bounds. It also claims a lower bound: some unit disk graphs require biclique covers of size Ω(n^{4/3}), answering a question of Tóth. The upper-bound arguments are largely self-contained, while the lower-bound section relies on a point-halfplane incidence construction and a reduction to unit disks.","tokens_in":22372,"tokens_out":3113,"duration_ms":31601,"significance":"If the upper-bound results stand, they provide a clean unifying framework for many previously scattered results and give new algorithmic implications via known reductions to matching and shortest paths. The proofs of Theorems 6, 8, 13, 16, 17, 21, 22, and 24 are elegant and mostly self-contained, with only standard external tools (Szemerédi-Trotter, Tomon's DNF equivalence). The claimed lower bound for unit disk graphs would be a significant negative answer to Tóth's question and would delineate the boundary between semilinear and semialgebraic graphs. However, the lower-bound section as written contains serious gaps that leave the central negative result unproved.","major_comments":[{"comment":"The proof of Claim 1 is incorrect as stated. The claimed dichotomy \"either p is incident to only one line, or ℓ contains only one point\" is false. For example, take the two lines y=0 and y=x with P={(0,0),(1,0)}. The point p=(0,0) is incident to both lines, yet the line y=0 contains another point of P, and all points lie in the intersection of the two closed lower halfplanes. Thus the leftmost-incidence argument does not go through. Since the intended induction (attributed to Erickson [43]) is not supplied, the claimed bound ι(Pi,Li) ≤ |Pi|+|Li| is unsupported, and consequently the Ω(n^{4/3}) lower bound for point-halfplane incidence graphs is not established.","section":"Section 6, Lemma 26, Claim 1"},{"comment":"The reduction from point-halfplane incidences to unit disk intersection graphs is not rigorous. The proof shifts lines upward and replaces them by circles of very large radius, but it gives no quantitative estimates. A unit disk tangent to a line contains points only below a parabola; to realize the incidences exactly, one needs a spread-separation tradeoff of the form R ≳ D^2/δ, where D is the global diameter and δ the minimum separation between points and non-incident lines. The proof provides no construction or error control, so the claimed realization of I(P,H) as a unit disk graph is not established. Since this lemma is the basis for the negative answer to Tóth's question, the central lower-bound result is unproved.","section":"Section 6, Lemma 27"},{"comment":"The proof relies on the statement that every semilinear graph of complexity t is dnf-semilinear of complexity (t',ℓ) with t' and ℓ depending only on t, attributed to Tomon [79] without proof or parameter bounds. Because this equivalence is load-bearing for the reduction to comparability bigraphs, the paper should either provide a proof, state the precise parameter dependence, or cite a specific theorem with full statement. As written, a reader cannot verify that the O(n polylog n) bound follows from the given definition of complexity.","section":"Section 3, proof of Theorem 8"}],"minor_comments":[{"comment":"There is a typo: \"let R′ ⊆ R be the of vertices r ∈ R\" should read \"let R′ ⊆ R be the set of vertices r ∈ R\".","section":"Section 2, proof of Theorem 6"},{"comment":"In the definition of Sb_1 and Sb_2, the text says \"short red intervals in Sb_v\", but Sb_v is the blue short list; these should be \"short blue intervals\".","section":"Section 5.5, proof of Theorem 24"},{"comment":"The phrase \"This improves on results by Tomon and Zakharov [80] and Basit et al. [14] by a factor log^d n\" is imprecise: those works give different bounds (polylog factors in the Zarankiewicz context), and the comparison should be stated more carefully to avoid implying a direct improvement in the same parameter.","section":"Section 5.4, Theorem 22"},{"comment":"The notation I(P,H) is used for the incidence graph of points and halfplanes, but the proof then refers to ι(P,L) for lines; the relationship between the halfplanes H and the set of lines L should be made explicit to avoid confusion.","section":"Section 6, Lemma 26"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound portion of the paper is strong and likely publishable after revision; the proofs of the main theorems are self-contained and elegant. The lower-bound section is the main obstacle: Lemma 26's Claim 1 is demonstrably false as written, and Lemma 27's unit-disk realization lacks the necessary quantitative control. These are fixable in principle (e.g., by importing Erickson's actual proof and by adding a careful curvature/separation argument), but they are load-bearing for the paper's advertised negative answer to Tóth's question. The Tomon [79] dependency should be clarified. I recommend major revision rather than rejection because the central upper-bound claims are sound and the lower-bound gaps appear local and repairable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The upper-bound half of this paper is solid and genuinely useful. Theorem 8, giving O(n polylog n) biclique covers for all constant-complexity semilinear graphs, is a real unification: it subsumes interval graphs, permutation graphs, bounded-boxicity graphs, and L-shape intersection graphs in one clean argument. The proof is self-contained except for the standard reduction to dnf-semilinear form from Tomon, which is cited properly. The capped-graph result (Theorem 13) is also nice, and the proof via two-dimensional comparability bigraphs is elementary and convincing. I checked the induction in Theorem 6 and the terrain-like recursion; both work. The paper also earns credit for the survey material and for being honest about which parts are not new (Section 5.4).\n\nNow the soft spots, in proportion. The lower-bound section is not in the same shape. Lemma 26's Claim 1 is asserted with a one-line argument that is simply false as stated: the claim that if a point is on two lines then one of those lines contains no other point does not hold in general. The intended charging argument may be repairable, but it is not here. Lemma 27 is even looser: replacing lines by very large circles and then scaling to unit disks requires quantitative control over how close the points are to the lines versus the disk curvature, and the proof gives no such estimates. The reduction from halfplane incidences to unit-disk intersection graphs is exactly where Toth's question gets answered, and this is the load-bearing step. So the headline negative answer to Toth's question is not established by this version.\n\nThe stress-test note is right on both counts. I also confirm the paper itself flags none of this; the lower-bound section reads as if the hard part is already done, when it is not.\n\nWho is this for? Anyone working on compact representations of geometric graphs, incidence bounds, or graph sparsification. The upper bounds alone make it worth a serious referee. The lower bound should be treated as conditional and sent back for a rigorous proof or a weakened claim.\n\nMy recommendation: send it to peer review, but tell the authors the unit-disk lower bound needs either a complete proof with the missing geometric estimates or removal from the paper. The rest can be accepted after minor revision.","headline":"Strong upper-bound paper with a lower-bound section that doesn't hold up as written; the semilinear and terrain-like results are worth refereeing, the unit-disk claim needs real work.","tokens_in":22950,"tokens_out":774,"would_cite":true,"duration_ms":10366,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C62","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Semilinear graphs of constant complexity have biclique covers of size $O(n \\operatorname{polylog} n)$; capped graphs get $O(n \\log^3 n)$; some unit disk graphs force $\\Omega(n^{4/3})$.","keywords":["biclique cover","biclique partition","semilinear graph","comparability bigraph","capped graph","terrain-like graph","visibility graph","unit disk graph"],"falsifier":"Take the standard tight point-line configurations on $n$ points and $n$ lines, shift the lines upward slightly, replace them by very large circles, and scale to unit disks; if any biclique cover of the resulting unit disk graph had size $o(n^{4/3})$, the lower-bound claim would be wrong. On the upper-bound side, the decisive check is the quoted reduction: prove or disprove that every constant-complexity semilinear graph is dnf-semilinear with both the number of clauses and the number of linear functions per clause depending only on the original complexity.","tokens_in":21911,"feed_emoji":"📐","tokens_out":9016,"duration_ms":91587,"temperature":0.7,"pith_summary":"Graphs can be stored compactly by covering their edges with complete bipartite subgraphs, where the cost is the total number of vertices over all bicliques; small covers make matching, shortest paths, and spanners faster. The paper's main theorem says every semilinear graph of constant complexity—any graph whose edges are decided by a fixed set of linear inequalities in a fixed dimension—admits a biclique cover of size $O(n \\operatorname{polylog} n)$. This single statement generalizes earlier near-linear covers for interval graphs, permutation graphs, bounded-boxicity graphs, and L-shape intersection graphs, and it implies the known semilinear Zarankiewicz bound. The paper also gives an elementary proof that capped (terrain-like) ordered graphs admit biclique partitions of size $O(n \\log^3 n)$, a combinatorial analogue of the classical compact-representation result for polygon visibility graphs. Finally, it constructs unit disk graphs whose biclique covers all have size $\\Omega(n^{4/3})$, answering a question about whether such graphs could have near-linear covers.","feed_headline":"Semilinear graphs get near-linear biclique covers","feed_subtitle":"One theorem covers interval, permutation, L-shape and boxicity-bounded graphs; terrain-like graphs get $O(n \\log^3 n)$.","key_machinery":"The central object is the biclique cover (or partition) of a graph, sized as the sum of $|V(H)|$ over the bicliques $H$. The mechanism that carries the semilinear-graph argument is the $d$-dimensional comparability bigraph: points in $\\mathbb{R}^d$ with an edge from left to right when one $d$-tuple is coordinate-wise smaller than the other. Each conjunction of linear inequalities is rewritten as such a dominance condition, and Theorem 6 partitions any $d$-dimensional comparability bigraph in $O(n \\log^d n)$ by splitting along one coordinate and recursing. For capped graphs, the key lemma identifies every capped bigraph with a two-dimensional comparability bigraph by assigning each vertex coordinates that encode its first and last neighbours, turning the forbidden-pattern condition into a dominance test.","core_discovery":"On its own terms, the paper establishes that semilinear graphs of constant complexity are a class of geometric graphs that can be compressed: every such graph on $n$ vertices has a biclique cover of size $O(n \\operatorname{polylog} n)$. The proof routes through dnf-semilinear forms: a conjunction of linear inequalities $f_{i,j}(x,y)<0$ is rewritten as $g_i(x) \\prec -h_i(y)$, so across any split of the vertex set the edges form two $t$-dimensional comparability bigraphs, and the recursive construction of Theorem 6 partitions each in $O(n \\log^t n)$. For capped graphs, the paper shows every capped bigraph is a two-dimensional comparability bigraph and then applies the same recursion, yielding an $O(n \\log^3 n)$ biclique partition. On the lower-bound side, it shows that incidence graphs of points and closed lower halfplanes, and hence unit disk graphs, can require biclique covers of size $\\Omega(n^{4/3})$, so near-linear covers cannot be expected once defining functions are allowed to be quadratic.","pith_inferences":["Because the semilinear proof is constructive, the same argument likely yields fast approximation algorithms for geometric intersection graphs beyond the classes explicitly named; this is an extrapolation, not a paper claim.","The unit-disk lower bound suggests a degree threshold: near-linear biclique covers are possible when all defining functions are linear, while quadratic functions already force $\\Omega(n^{4/3})$-size covers; the paper states a similar expectation for translates of smooth strictly convex bodies.","The identification of capped bigraphs with two-dimensional comparability bigraphs is likely to transfer algorithmic machinery from permutation graphs to terrain-visibility problems; the paper leaves this transfer implicit."],"forward_implications":["Corollary 9 follows directly: every $K_{t,t}$-free semilinear graph of constant complexity has $O(n \\operatorname{polylog} n)$ edges, recovering the Zarankiewicz bound of [14].","Every semilinear graph has a 3-hop spanner with $O(n \\operatorname{polylog} n)$ edges, by Lemma 4 applied to the cover.","For semilinear graphs, the cover can be computed in $O(n \\operatorname{polylog} n)$ time, so maximum matching runs in $O(n^{1+\\varepsilon})$ and all-pairs shortest paths in $O(n^2 \\operatorname{polylog} n)$.","Every capped graph has a biclique partition of size $O(n \\log^3 n)$, computable in $O(\\max\\{|E|, n \\log^3 n\\})$ time from sorted adjacency lists, giving a BFS tree in $O(n \\log^3 n)$ per root after preprocessing.","There are unit disk graphs on $n$ vertices with no biclique cover of size $o(n^{4/3})$, so near-linear covers cannot be expected for semialgebraic graphs of degree two."],"supporting_citations":[{"why":"Introduces semilinear graphs and proves the Zarankiewicz bound that the main theorem rederives as a corollary.","marker":"[14]"},{"why":"Supplies the dnf-semilinear equivalence on which the proof of Theorem 8 is built.","marker":"[79]"},{"why":"Establishes biclique covers as compressed graph representations and gives the algorithmic speedups for BFS and matching used in the applications.","marker":"[45]"},{"why":"Defines capped graphs via the forbidden four-vertex pattern that is the object of the terrain-like theorem.","marker":"[38]"},{"why":"Proves the classical compact-representation result for polygon visibility graphs that the capped-graph theorem is patterned on.","marker":"[3]"},{"why":"Records the Szemerédi–Trotter incidence bound and its tight configurations used for the unit-disk lower bound.","marker":"[69]"}],"fun_headline_variants":["Near-linear biclique covers for semilinear graphs","Terrain-like graphs admit O(n log^3 n) biclique partitions","Unit disk graphs require large biclique covers","Semilinear graphs compress into near-linear bicliques","No near-linear biclique cover for unit disk graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The semilinear-graph theorem rests on a cited result that every semilinear graph of constant complexity can be rewritten in disjunctive normal form with constants depending only on the original complexity; the paper quotes this result without proving it or stating the parameter bounds.","fun_headline_variants_meta":{"raw":{"variants":["Near-linear biclique covers for semilinear graphs","Terrain-like graphs admit O(n log^3 n) biclique partitions","Unit disk graphs require large biclique covers","Semilinear graphs compress into near-linear bicliques","No near-linear biclique cover for unit disk graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000966,"raw_usage":{"total_tokens":4220,"prompt_tokens":1162,"completion_tokens":3058,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":778,"completion_tokens_details":{"reasoning_tokens":2976}},"tokens_in":778,"tokens_out":3058,"duration_ms":24131,"temperature":1.0,"reasoning_tokens":2976,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:24:42.993590+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the standard tight point-line configurations on $n$ points and $n$ lines, shift the lines upward slightly, replace them by very large circles, and scale to unit disks; if any biclique cover of the resulting unit disk graph had size $o(n^{4/3})$, the lower-bound claim would be wrong. On the upper-bound side, the decisive check is the quoted reduction: prove or disprove that every constant-complexity semilinear graph is dnf-semilinear with both the number of clauses and the number of linear functions per clause depending only on the original complexity.","supporting_citations":[{"cited_title":"Zarankiewicz’s problem for semilinear hypergraphs","cited_arxiv_id":null,"evidence_quote":"Introduces semilinear graphs and proves the Zarankiewicz bound that the main theorem rederives as a corollary."},{"cited_title":"Ramsey properties of semilinear graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the dnf-semilinear equivalence on which the proof of Theorem 8 is built."},{"cited_title":"Clique partitions, graph compression and speeding-up algorithms","cited_arxiv_id":null,"evidence_quote":"Establishes biclique covers as compressed graph representations and gives the algorithmic speedups for BFS and matching used in the applications."},{"cited_title":"Coloring polygon visibility graphs and their generalizations","cited_arxiv_id":null,"evidence_quote":"Defines capped graphs via the forbidden four-vertex pattern that is the object of the terrain-like theorem."},{"cited_title":"Incidences","cited_arxiv_id":null,"evidence_quote":"Records the Szemerédi–Trotter incidence bound and its tight configurations used for the unit-disk lower bound."}],"review_version":1}