On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

Chalermsook, Parinya; Orgo, Ly; Zarsav, Minoo

doi:10.4230/LIPIcs.GD.2025.21

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

Parinya Chalermsook

University of Sheffield, England Ly Orgo

Aalto University, Finland Minoo Zarsav

Aalto University, Finland

Abstract

This paper considers the Zarankiewicz problem in bipartite graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). ¹¹1Ferrers dimension, along with interval dimension and order dimension, is a standard dimensional concept in graphs. Please refer to the introduction for formal definition. Let $Z(n;k)$ be the maximum number of edges in a bipartite graph with $n$ nodes and is free of a $k$ -by- $k$ biclique. Note that $Z(n;k)\in\Omega(nk)$ for all “natural” graph classes. Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while we show that $Z(n;k)\leq 9n(k-1)$ for graphs of Ferrers dimension three, $Z(n;k)\in\Omega\left(nk\cdot\frac{\log n}{\log\log n}\right)$ for Ferrers dimension four graphs (Chan & Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of $2n(k-1)$ for chordal bipartite graphs and $54n(k-1)$ for grid intersection graphs (GIG), a prominent graph class residing in four Ferrers dimensions and capturing planar bipartite graphs as well as bipartite intersection graphs of rectangles. Previously, the best-known bound for GIG was $Z(n;k)\in O(2^{O(k)}n)$ , implied by the results of Fox & Pach (2006) and Mustafa & Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics.

Keywords and phrases:

Bipartite graph classes, extremal graph theory, geometric intersection graphs, Zarankiewicz problem, bicliques

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms

Funding:

This work was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 759557).

DOI:

10.4230/LIPIcs.GD.2025.21

Event:

33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Editors:

Vida Dujmović and Fabrizio Montecchiani

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Bipartite graphs are the most natural mathematical objects used to capture interrelations between two groups of interest. Therefore, it is unsurprising that they arise routinely in mathematical and algorithmic research communities. In extremal graph theory, bipartite graphs have been studied extensively from several perspectives.

The Zarankiewicz problem is perhaps among the oldest questions in extremal graph theory. In 1951, Zarankiewicz asked for the maximum number of edges in a bipartite graph with $n$ nodes on each side that does not contain a complete bipartite subgraph $K_{k,k}$ . ²²2Here, we are interested in a symmetric form of the Zarankiewicz problem. A more general question can involve graphs with different numbers of vertices on each side, that do not contain some biclique $K_{s,t}$ . Equivalently, given an $n$ -by- $n$ matrix with 0/1 entries, that does not contain a $k$ -by- $k$ all-one submatrix, what is the maximum number of $1$ -entries in such a matrix? This question was partially answered by Kövari, Sós and Turán: If we denote such number by $Z(n;k)$ , it was proven that $Z(n;k)\in O(n^{2-1/k})$ [20], and the best known lower bound is $\widetilde{\Omega}(n^{2-2/(k+1)})$ shown in [2]. Exact values are known for $k=2$ , $k=3$ , and closing the gap for $k\geq 4$ is one of the central open questions in extremal combinatorics. A trivial lower bound would be $n\cdot k$ , achieved by $K_{k,n}$ .

This question has also attracted significant interest in the context of specific graph classes, particularly those with additional structural constraints [4, 25, 12]. Chan and Har-Peled, for instance, studied a wide range of geometrically defined bipartite graphs [4], such as incidence graphs of points and rectangles, disks, or pseudodisks.

1.1 Our contributions

We consider the Zarankiewicz problem for geometric bipartite graphs. For “natural” graph classes, the lower bound of $Z(n;k)\in\Omega(nk)$ holds trivially. Our results show that a nearly tight upper bound can be achieved for many natural graph classes.

To formalize the discussion, consider a bipartite intersection graph $G=(U\cup V,E)$ , defined by two families of objects ${\mathcal{F}}_{U}$ and ${\mathcal{F}}_{V}$ , where each vertex $u\in U$ (resp. $v\in V$ ) is associated with an object $O_{u}\in{\mathcal{F}}_{U}$ (resp. $O_{v}\in{\mathcal{F}}_{V}$ ); Let $\phi:u\mapsto O_{u},v\mapsto O_{v}$ for $u\in U$ and $v\in V$ be the bijection between vertices and their representations. We say that $({\mathcal{F}}_{U},{\mathcal{F}}_{V},\phi)$ is an intersection representation of $G$ . Whenever the mapping $\phi$ is clear from the context, we omit it. Table 1 shows bipartite intersection graphs relevant to this paper.

Table 1: Classes of bipartite intersection graphs that are relevant to this paper.

Graph Classes	Family ${\mathcal{F}}_{U}$	Family ${\mathcal{F}}_{V}$	domain
$\operatorname{\sf{CHAIN}}$	rightward rays	points	$\mathbb{R}$
$\operatorname{\sf{CONV}}$	intervals	points	$\mathbb{R}$
$\operatorname{\sf{CHAIN}}^{2}$	rightward rays	upward rays	$\mathbb{R}^{2}$
$\operatorname{\sf{SR}}$	horizontal segments	upward rays	$\mathbb{R}^{2}$
$\operatorname{\sf{GIG}}$	horizontal segments	vertical segments	$\mathbb{R}^{2}$
$\operatorname{\sf{PRIG}}$	axis-aligned rectangles	points	$\mathbb{R}^{2}$

For two graph classes ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$ , we use ${\mathcal{C}}_{1}\cdot{\mathcal{C}}_{2}$ to denote the class of graphs, such that every graph $G\in{\mathcal{C}}_{1}\cdot{\mathcal{C}}_{2}$ is the intersection of some graphs $G_{1}\in{\mathcal{C}}_{1}$ , $G_{2}\in{\mathcal{C}}_{2}$ , where intersection between graphs is defined as the intersection between their nodes and edges. When ${\mathcal{C}}_{1}={\mathcal{C}}_{2}$ , we use the notation ${\mathcal{C}}_{1}^{2}={\mathcal{C}}_{1}\cdot{\mathcal{C}}_{1}$ , and similarly for other powers.

The concept of Ferrers dimension is crucially based on chain graphs ( $\operatorname{\sf{CHAIN}}$ ). A bipartite graph $G=(U\cup V,E)$ is in $\operatorname{\sf{CHAIN}}$ if it is an intersection graph of rays and points on the line [7]. Ferrers dimension of a bipartite graph $G$ , denoted by $\sf{fd}(G)$ , is the smallest integer $d$ , such that $G\in\operatorname{\sf{CHAIN}}^{d}$ . It is known that every $n$ -vertex graph has Ferrers dimension at most $n$ .

We will use $Z_{{\mathcal{C}}}(n,m;k,k)$ to denote the maximum number of edges in a bipartite graph $G=(U\cup V,E)\in{\mathcal{C}}$ , where $|U|=n$ , $|V|=m$ , such that the graph does not contain $K_{k,k}$ as a subgraph, and simply $Z_{{\mathcal{C}}}(n;k)$ , when $n=m$ .

Our first main result provides a dichotomy between Ferrers dimension three and four.

Theorem 1 (Dichotomy theorem).

The following dichotomy results hold for all $k\in\mathbb{N}$ :

$\blacksquare$

$Z_{\operatorname{\sf{CHAIN}}^{3}}(n;k)\leq 9n(k-1)$ .
$\blacksquare$

$Z_{\operatorname{\sf{CHAIN}}^{4}}(n;k)\in\Omega(nk\cdot\frac{\log n}{\log\log n})$ .

By using our upper bound for Ferrers dimension three as a base case, a result by Chan and Har-Peled [4] can be improved (proof in Appendix A).

Corollary 2.

For graphs of Ferrers dimension $d\geq 3$ , $k\in\mathbb{N}$ , we have $Z_{\operatorname{\sf{CHAIN}}^{d}}(n;k)\leq O(nk\cdot\lceil\log n\rceil^{d-3})$ .

We complement the lower bound for $\operatorname{\sf{CHAIN}}^{4}$ by providing Zarankiewicz upper bounds for a prominent graph class in $\operatorname{\sf{CHAIN}}^{4}$ .

Theorem 3.

For all $k,n\in\mathbb{N}$ , $Z_{\operatorname{\sf{GIG}}}(n;k)\leq 54n(k-1)$ .

This is our second main result. Grid intersection graph (GIG) is an intersection graph of horizontal and vertical segments in ${\mathbb{R}}^{2}$ . This graph class contains all graphs of Ferrers dimension two and is known to be in $\operatorname{\sf{CHAIN}}^{4}$ . GIG is rich, includes all planar bipartite graphs, and is equivalent to the bipartite intersection graphs of rectangles [1]. They have been studied from both structural and algorithmic perspectives [8, 22, 21]. This result improves upon the $2^{O(k)}n$ upper bound that follows from [25, 13] (their results hold for more general intersection graphs of curves).³³3Note that Fox and Pach explicitly mentioned the term $2^{O(k)}$ , while Mustafa and Pach’s dependency on $k$ is somewhat hidden in their calculation. Looking at their calculations reveals that the constant is $2^{O(k)}$ .

Our final result applies to chordal bipartite graphs – a bipartite graph is chordal if every cycle of length at least six contains a chord. Chordal bipartite graphs contain all graphs of Ferrers dimension at most two. On the other hand, it is relatively rich, having unbounded Ferrers dimension [7, 6].

Theorem 4.

For all $k,n\in\mathbb{N}$ , $Z_{{\mathcal{C}}}(n;k)\leq 2n(k-1)$ , where ${\mathcal{C}}$ is a class of chordal bipartite graphs.

We observe that $Z_{\operatorname{\sf{CHAIN}}}(n;k)\geq 2n(k-1)-O(k^{2})$ even for $\operatorname{\sf{CHAIN}}$ (see Lemma 38 in Appendix E), so our upper bound is tight up to an additive constant for fixed $k$ . Theorem 4 improves upon the $4nk$ upper bound that holds for $\operatorname{\sf{CONV}}$ [4] (since such graphs have Ferrers dimension at most two). Please refer to Table 2 for a comprehensive list of our results and Figure 1 for a landscape of $Z_{{\mathcal{C}}}(n;k)$ , when ${\mathcal{C}}$ is one of these graph chasses.

Table 2: Zarankiewicz Bounds proved in this paper. Our bounds follow from Theorem 4, Corollary 13, Corollary 19, and Theorem 3 respectively.

Graph classes	Our UB	Known UB
Chordal bipartite graphs	$2n(k-1)$	$3kn$ for a special case. [4]
Segment ray graphs (SR)	$4n(k-1)$	$O(kn)$ [4]
$\operatorname{\sf{CHAIN}}^{3}$	$9n(k-1)$
Grid intersection graphs (GIG)	$54n(k-1)$	$2^{O(k)}n$ [13, 25]

Figure 1: The relation between graph classes considered in this paper. All inclusions denoted by arrows are known to be proper. Our results imply the separation shown by the dotted curve. We show that

\operatorname{\sf{CHAIN}}^{3}

,

\operatorname{\sf{GIG}}

, and chordal bipartite graphs satisfy

Z_{{\mathcal{C}}}(n;k)\in O(nk)

, which implies the same for the rest of the graph classes below them.

We remark that all our upper bounds are algorithmic in the sense that, given a graph and its geometric representation in class ${\mathcal{C}}$ , we give an efficient algorithm that reports a $k$ -by- $k$ biclique whenever the number of edges exceeds our $Z_{{\mathcal{C}}}(n;k)$ upper bound (e.g., given a grid intersection graph ${\mathcal{C}}=\operatorname{\sf{GIG}}$ with more than $54(k-1)n$ edges, our algorithm efficiently finds a $k$ -by- $k$ biclique).

Comparison to known results.

Prior to our results, the upper bound $Z_{{\mathcal{C}}}(n;k)\in O(nk)$ has been known for $\operatorname{\sf{CONV}}$ , segments and rays⁴⁴4Chan and Har-Peled use the equivalent 3-sided rectangle and point intersection graphs., and halfspaces and points [4]. We improve a constant for $\operatorname{\sf{CONV}}$ (since it is a special case of chordal bipartite graphs) and generalize their result on the segment-ray graphs to grid intersection graphs. The grid intersection graph is a special case of string graphs, so the upper bound [13, 25] of $Z_{\operatorname{\sf{GIG}}}(n;k)\in O(2^{O(k)}n)$ follows from their results on string graphs. Please refer to Figure 1 for the relations between these classes.

Further related works.

The graph classes in this paper have received much attention from various perspectives, including recognition algorithms, optimization, and structures. For instance, chordal bipartite graphs have been considered in [23, 15, 24, 30]. For grid intersection graphs, the recognition problem is NP-complete [21, 22]. The class is known to capture planar bipartite graphs [16] and is equivalent to the intersection graph of rectangles that are bipartite [1]. For more detailed literature on GIG, we refer the readers to an exposition in the PhD thesis of Mustata [26].

Zarankiewicz problems have been studied in many other special graphs, such as semi-algebraic graphs [14, 10], graphs of bounded VC dimension [17], graphs forbidding a fixed induced subgraph [3], and in geometric intersection graphs [18, 5, 4, 29, 5]. We refer to the recent survey by Smorodinsky for a more comprehensive list of related works [28].

2 Preliminaries

We use standard graph-theoretic notation. A bipartite graph is denoted as $G=(U\cup V,E)$ where $U$ and $V$ are partitions of the vertices. For a graph $G$ , we refer to its set of vertices as $V(G)$ , its set of edges as $E(G)$ , and its induced subgraph on $S\subseteq V(G)$ as $G[S]$ .

The intersection of two graphs $G_{1}$ and $G_{2}$ is defined as $G_{1}\cap G_{2}=(V(G_{1})\cap V(G_{2}),E(G_{1})\cap E(G_{2}))$ . When $G_{1}$ belongs in graph class ${\mathcal{C}}_{1}$ and $G_{2}$ in class ${\mathcal{C}}_{2}$ , then we say that $G_{1}\cap G_{2}$ belongs in ${\mathcal{C}}_{1}\cdot{\mathcal{C}}_{2}$ . For graph classes ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$ , that are closed under taking induced subgraphs, a graph $G\in{\mathcal{C}}_{1}\cdot{\mathcal{C}}_{2}$ can be assumed to be the intersection of two graphs on the same vertex set, because if $G_{1}\in{\mathcal{C}}_{1}$ , then $G_{1}[V(G_{2})\cap V(G_{1})]\in{\mathcal{C}}_{1}$ . Similarly for $G_{2}$ .

Therefore, for two graph classes ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$ that are closed under taking induced subgraphs, the intersection of the graph classes can be defined as:

{\mathcal{C}}_{1}\cdot{\mathcal{C}}_{2}=\{G_{1}\cap G_{2}:V(G_{1})=V(G_{2}),G_% {1}\in{\mathcal{C}}_{1},G_{2}\in{\mathcal{C}}_{2}\}

One can naturally write ${\mathcal{C}}^{d}={\mathcal{C}}\cdot{\mathcal{C}}\ldots{\mathcal{C}}$ ( $d$ times).

Bicliques are the graphs $K_{a,b}$ , where $a$ and $b$ are some positive integers.

Proposition 5.

If the graph class ${\mathcal{C}}$ contains every biclique, then ${\mathcal{C}}\subseteq{\mathcal{C}}^{2}\subseteq\ldots$ .

Proof.

Here, we show that for any positive integer $i$ , ${\mathcal{C}}^{i}\subseteq{\mathcal{C}}^{i+1}$ . Let $G=(U\cup V,E)\in{\mathcal{C}}^{i}$ . Then take $H$ being the complete bipartite graph on $U$ and $V$ (where the edges connect vertices in $U$ and $V$ ). Then $H\in{\mathcal{C}}$ . Therefore, $G=G\cap H\in{\mathcal{C}}^{i+1}$ . $\hfill\blacktriangleleft$

Since $\operatorname{\sf{CHAIN}}$ contains every biclique, this implies that $\operatorname{\sf{CHAIN}}\subseteq\operatorname{\sf{CHAIN}}^{2}\subseteq\ldots$ . It is known that $\operatorname{\sf{CHAIN}}^{2}$ is equivalent to the class of all two-directional orthogonal ray graphs (2DOR) [7, Theorem 2.1].

A bipartite graph $G=(U\cup V,E)$ is convex over $V$ if there exists an ordering $V=\{v_{1},\ldots v_{|V|}\}$ such that for all $u\in U$ , the vertices $N(u)$ are contiguous ( $\{v_{i},\ldots v_{j}\}$ for some $i,j\in[|V|]$ ). We call the set of such graphs $\operatorname{\sf{CONV}}$ . $\operatorname{\sf{CONV}}$ is known to be equivalent to a containment graph of points and intervals in $\mathbb{R}$ . An interesting graph class worth mentioning is $\operatorname{\sf{CONV}}^{2}$ – the intersection of two convex graphs.

Theorem 6.

A bipartite graph $G=(U\cup V,E)$ is in $\operatorname{\sf{CONV}}^{2}$ if and only if $G$ is a disjoint union of $\operatorname{\sf{GIG}}$ and $\operatorname{\sf{PRIG}}$ graphs.

The proof can be found in Appendix B.

Finally, a bipartite graph is a chordal bipartite graph if every induced cycle of length at least six contains a chord. It is known that chordal bipartite graphs can have unbounded Ferrers dimension [7, 6].

3 Warm-up

Recall that a graph $G$ is $d$ -degenerate if every induced subgraph has a vertex of degree at most $d$ . All graph classes considered in this paper are closed under taking induced subgraphs.

Observation 7.

A $d$ -degenerate graph $G$ has at most $d\cdot|V(G)|$ edges.

3.1 Chordal bipartite graphs

For a bipartite graph $G$ , denote its biadjacency matrix by $M_{G}$ . We say that a matrix $M$ contains submatrix $P$ if we can obtain $P$ by removing some rows and columns of $M$ . A matrix $M$ is $P$ -free if it does not contain submatrix $P$ . A bipartite graph $G$ is $P$ -freeable, if there exists an ordering of rows and columns, such that the biadjacency matrix $M_{G}$ is $P$ -free.

The following structural result is known for chordal bipartite graphs.

Theorem 8 ([19, 11]).

Every chordal bipartite graph is $\begin{pmatrix}0&1\\ 1&1\end{pmatrix}$ -freeable.

Lemma 9.

For any $k\in\mathbb{N}$ , a chordal bipartite graph that does not contain $K_{k,k}$ is $(k-1)$ -degenerate.

Proof.

Let $H$ be a chordal bipartite graph. If for every induced subgraph of $H$ , a node of degree at most $k-1$ exists, we are done. Therefore, let us assume by contradiction that $G$ is an induced subgraph of $H$ , where a node of degree at most $k-1$ does not exist. Then all nodes $V(G)$ have a degree of at least $k$ in $G$ . Using Theorem 8, we know that there is a $P$ -free biadjacency matrix of $G$ , where $P=\begin{pmatrix}0&1\\ 1&1\end{pmatrix}$ . Let $M_{G}$ be that biadjacency matrix. Let $G=(U\cup V,E)$ , where each row $i\in[|U|]$ and column $j\in[|V|]$ correspond to the vertices $u_{i}\in U$ and $v_{j}\in V$ , respectively. Let $i\in[|U|]$ be the maximum integer, such that $M_{G}(i,|V|)=1$ (i.e., this is the bottommost row in the last column such that the entry is one). Consider the rows $R=\{i^{\prime}:u_{i^{\prime}}\in N_{G}(v_{|V|})\}\subseteq[|U|]$ and columns $C=\{j^{\prime}:v_{j^{\prime}}\in N_{G}(u_{i})\}\subseteq[|V|]$ .

Figure 2: An example, where rows

R

are denoted in purple and columns

C

in green.

Let $M^{\prime}$ be the submatrix induced on rows $R$ and columns $C$ . According to our assumption, this submatrix $M^{\prime}$ contains at least $k$ rows and $k$ columns. It is easy to see that $M^{\prime}$ is an all-one matrix: Assume that it is not, and $M_{G}(a,b)=0$ for some $a\in R$ and $b\in C$ . Since $a\in R$ , we have $M_{G}(a,|V|)=1$ and since $b\in C$ , $M_{G}(i,b)=1$ . The $2$ -by- $2$ submatrix induced on rows $\{a,i\}$ and columns $\{b,|V|\}$ is then equal to the forbidden pattern $P$ , a contradiction. $\hfill\blacktriangleleft$

Theorem 10.

For all $n,m,k\in\mathbb{N}$ , $Z_{{\mathcal{C}}}(m,n;k,k)\leq(m+n)(k-1)$ , where ${\mathcal{C}}$ is the class of chordal bipartite graphs.

Proof.

The result follows from Lemma 9 and Observation 7. $\hfill\blacktriangleleft$

The matching lower bound is shown in Lemma 38.

Theorem 4. [Restated, see original statement.]

For all $k,n\in\mathbb{N}$ , $Z_{{\mathcal{C}}}(n;k)\leq 2n(k-1)$ , where ${\mathcal{C}}$ is a class of chordal bipartite graphs.

Proof.

The result follows from Theorem 10 when $n=m$ . $\hfill\blacktriangleleft$

3.2 Segment ray graphs

Next, we present a simple proof of the upper bound of $Z_{\operatorname{\sf{SR}}}(m,n;k,k)$ for the intersection graph of horizontal segments and vertical upward rays in ${\mathbb{R}}^{2}$ , denoted by $\operatorname{\sf{SR}}$ . More precisely, $({\mathcal{S}},{\mathcal{R}},\phi)$ , is a segment ray ( $\operatorname{\sf{SR}}$ ) representation of a bipartite graph $G=(U\cup V,E)$ , if ${\mathcal{S}}$ and ${\mathcal{R}}$ are sets of horizontal segments and vertical upwards rays in $\mathbb{R}^{2}$ respectively, and $\phi:U\mapsto{\mathcal{S}},V\mapsto{\mathcal{R}}$ , such that $\{u,v\}\in E$ , where $u\in U$ , $v\in V$ , if and only if $\phi(u)$ and $\phi(v)$ intersect.

Although the upper bound $O((m+n)k)$ was shown in [4], we improve this upper bound to $2(m+n)(k-1)$ .

Lemma 11.

Every segment-ray graph that does not contain $K_{k,k}$ is $2(k-1)$ -degenerate.

Proof.

Let $H$ be a segment-ray graph. If, for every induced subgraph of $H$ , a node of degree at most $2(k-1)$ exists, we are done. Therefore, let us assume by contradiction, that $G$ is an induced subgraph of $H$ , where a node of degree at most $2(k-1)$ does not exist. Then, all nodes $V(G)$ must have a degree at least $2k-1$ in $G$ .

Let $({\mathcal{S}},{\mathcal{R}},\phi)$ be the $\operatorname{\sf{SR}}$ representation of $G=(U\cup V,E)$ , such that $\phi:U\mapsto{\mathcal{S}},V\mapsto{\mathcal{R}}$ . Let $x$ and $y$ be the horizontal and vertical axes, respectively. Each ray $r\in{\mathcal{R}}$ can be addressed by a pair $(r_{x},r_{y})$ , where $r_{x}$ and $r_{y}$ are the $\mathbf{x}$ and $\mathbf{y}$ coordinates of its starting point respectively. Each horizontal segment $s\in{\mathcal{S}}$ can be addressed using three variables $(s_{l},s_{r},s_{y})$ , such that $[s_{l},s_{r}]$ and $s_{y}$ are the projections of $s$ to the $x$ and $y$ axis respectively.

Let $r\in{\mathcal{R}}$ be the ray with the largest $r_{y}$ (highest starting point). Let $S$ be the set of segments that intersect $r$ . Then, according to our assumption, $|S|\geq 2k-1$ . Let $S_{right}\subseteq S$ be the set of $k-1$ segments with the largest (rightmost) $s_{r}$ , and let $S_{left}\subset S$ be the set of $k-1$ segments with the least (leftmost) $s_{l}$ . Then there must be at least one segment $s\in S\setminus(S_{right}\cup S_{left})$ (Figure 3).

Refer to caption — Figure 3: $R_{left}$ and $R_{right}$ are denoted by purple and green rays respectively.

Let $R$ be the set of rays that intersect $s$ . By our assumption, $|R|\geq 2k-1$ . Let $R_{left},R_{right}\subseteq R$ be the sets of rays to the left and right of $r$ , respectively. Since $R=R_{left}\cup R_{right}\cup\{r\}$ , then at least one of $R_{left},R_{right}$ must contain at least $k-1$ rays. Let us assume it is $R_{left}$ , the other case can be argued symmetrically. Since $r$ is the ray with the highest $r_{y}$ , then each ray in $R_{left}$ must intersect each segment in $S_{left}$ (Figure 3). This implies that the vertices mapped to rays in $R_{left}\cup\{r\}$ and segments in $S_{left}\cup\{s\}$ must induce a $k$ -by- $k$ biclique. This is a contradiction. $\hfill\blacktriangleleft$

Theorem 12.

For all $n,m,k\in\mathbb{N}$ , $Z_{\operatorname{\sf{SR}}}(m,n;k,k)\leq 2(m+n)(k-1)$ in segment ray graphs.

Proof.

The result follows from Lemma 11 and Observation 7. $\hfill\blacktriangleleft$

Corollary 13.

When $m=n$ , $Z_{\operatorname{\sf{SR}}}(n;k)\leq 4n(k-1)$ in segment ray graphs.

4 Graphs of Ferrers Dimension Three

This section presents the proof of the first part of Theorem 1.

Let $x$ and $y$ be the horizontal and vertical axes, respectively. We say that a rectangle $r$ in $\mathbb{R}^{2}$ is bottomless ⁵⁵5These rectangles have also been called $3$ -sided rectangles [4] in the context of $\operatorname{\sf{SR}}$ graphs. if its projection to the $y$ -axis is an interval that starts at $-\infty$ .

We say that $({\mathcal{S}},{\mathcal{B}},\phi)$ is a segment bottomless rectangle containment representation of a bipartite graph $G=(U\cup V,E)$ , if ${\mathcal{S}}$ and ${\mathcal{B}}$ are sets of horizontal segments and bottomless rectangles in $\mathbb{R}^{2}$ , respectively, $\phi:U\mapsto{\mathcal{S}},V\mapsto{\mathcal{B}}$ , and for all $u\in U$ , $v\in V$ , we have $\{u,v\}\in E$ if and only if $\phi(u)$ is contained within $\phi(v)$ . A bipartite graph $G$ is a segment bottomless rectangle containment graph, if it has a segment bottomless rectangle containment representation.

For $s\in{\mathcal{S}}\cup{\mathcal{B}}$ , let $s . x$ and $s . y$ denote the projections of $s$ to $x$ - and $y$ -axis respectively. For an interval $s.x=[a,b]$ , we use $\min(s.x)=a$ and $\max(s.x)=b$ to denote its minimum and maximum points.

Lemma 14.

A bipartite graph $G$ is of Ferrers dimension three ( $G\in\operatorname{\sf{CHAIN}}^{3}$ ) if and only if it is a segment bottomless rectangle containment graph.

The proof can be found in Appendix C.

Given a bipartite graph $G\in\operatorname{\sf{CHAIN}}^{3}$ , we now know it must have a containment representation $({\mathcal{S}},{\mathcal{B}},\phi)$ , where ${\mathcal{S}}$ and ${\mathcal{B}}$ are sets of horizontal segments and bottomless rectangles in $\mathbb{R}^{2}$ , and $\phi:U\mapsto{\mathcal{S}},V\mapsto{\mathcal{B}}$ .

Let $k$ be the minimum positive integer such that $G$ does not contain $K_{k,k}$ as a subgraph.

Without loss of generality, assume that no two horizontal segments have the same $y$ -coordinate. We define three (strict) partial orders (denoted by ${\mathcal{P}}^{DL}$ , ${\mathcal{P}}^{DR}$ , and ${\mathcal{P}}^{C}$ ) on ${\mathcal{S}}$ that will be crucial to our analysis (Figure 4). For $s,s^{\prime}\in{\mathcal{S}}$ , we say

$\blacksquare$

$s^{\prime}$ succeeds $s$ in the partial order ${\mathcal{P}}^{DL}$ , and denote it by $s\prec_{DL}s^{\prime}$ , if $\min(s^{\prime}.x)\leq\min(s.x)$ , $\max(s^{\prime}.x)\leq\max(s.x)$ , and $s^{\prime}.y<s.y$ ,
$\blacksquare$

$s^{\prime}$ succeeds $s$ in the partial order ${\mathcal{P}}^{DR}$ , and denote it by $s\prec_{DR}s^{\prime}$ , if $\min(s.x)\leq\min(s^{\prime}.x)$ , and $\max(s.x)\leq\max(s^{\prime}.x)$ , and $s^{\prime}.y<s.y$ ,
$\blacksquare$

$s^{\prime}$ succeeds $s$ in the partial order ${\mathcal{P}}^{C}$ , and denote it by $s\prec_{C}s^{\prime}$ , if $s^{\prime}.x\subset s.x$ .

It is easy to check that ${\mathcal{P}}^{DL}$ , ${\mathcal{P}}^{DR}$ , and ${\mathcal{P}}^{C}$ are transitive and asymmetric.

If $s\prec_{DL}s^{\prime}$ or $s^{\prime}\prec_{DL}s$ , we say that $s$ and $s^{\prime}$ are comparable in ${\mathcal{P}}^{DL}$ ; otherwise, they are incomparable. We can say the same about comparability in ${\mathcal{P}}^{DR}$ and ${\mathcal{P}}^{C}$ . The following claim is straightforward, and a consequence of a simple case analysis (see Figure 4).

Observation 15.

A pair of segments $s,s^{\prime}\in{\mathcal{S}}$ is comparable in one of the partial orders ${\mathcal{P}}^{DL},{\mathcal{P}}^{DR},{\mathcal{P}}^{C}$ .

For a segment $s\in{\mathcal{S}}$ , denote by $\operatorname{\sf{succ}}^{DL}(s),\operatorname{\sf{succ}}^{DR}(s),% \operatorname{\sf{succ}}^{C}(s)\subseteq{\mathcal{S}}$ the sets of all successors of $s$ with respect to partial orders ${\mathcal{P}}^{DL}$ , ${\mathcal{P}}^{DR}$ and ${\mathcal{P}}^{C}$ , respectively.

To count the number of edges in a bipartite graph $G$ with a representation $({\mathcal{S}},{\mathcal{B}},\phi)$ , we classify the edges into bulky and thin edges. For an edge $\{u,v\}\in E(G)$ , we have containment $\phi(u)\subseteq\phi(v)$ , where $\phi(u)\in{\mathcal{S}}$ , $\phi(v)\in{\mathcal{B}}$ . We say that the edge $\{u,v\}$ is DL-bulky if the bottomless rectangle $\phi(v)$ contains $k-1$ segments from $\operatorname{\sf{succ}}^{DL}(\phi(u))$ (See Figure 5). We can analogously define DR-bulky and C-bulky edges. All edges that are not bulky are called thin. An edge is bulky if it is DL-bulky, DR-bulky, or C-bulky.

If $s\prec_{DL}s^{\prime}$ or $s^{\prime}\prec_{DL}s$ , we say that $s$ and $s^{\prime}$ are comparable in ${\mathcal{P}}^{DL}$ ; otherwise, they are incomparable. We can say the same about comparability in ${\mathcal{P}}^{DR}$ and ${\mathcal{P}}^{C}$ . The following claim is straightforward, and a consequence of a simple case analysis (see Figure 4).

Lemma 16.

For each $u\in U$ , the number of bulky edges incident to $u$ of each type is at most $(k-1)$ . Therefore, at most $3(k-1)$ bulky edges are incident to each $u$ .

Proof.

We present the proof for DL-bulky edges. The proofs for the other two cases are similar. Let $B\subseteq N_{G}(u)$ be the nodes $v\in V$ , such that $\{u,v\}$ is DL-bulky. Let $S^{\prime}\subseteq\operatorname{\sf{succ}}^{DL}(\phi(u))$ be the $k-1$ segments $s^{\prime}\in S^{\prime}$ with the largest $\min(s^{\prime}.x)$ . Let $U^{\prime}$ be the set of nodes represented by $S^{\prime}$ .

We will show that each $v\in B$ has $\{u\}\cup U^{\prime}$ in its neighborhood, and therefore $|B|\leq k-1$ . Assume by contraposition that $|B|\geq k$ . Let $v\in B$ be an arbitrary node. For any $s^{\prime}\in S^{\prime}$ , $\phi(u)\prec_{DL}s^{\prime}$ and $\phi(u)\subseteq\phi(v)$ imply the following:

$\blacksquare$

$s^{\prime}.y\in\phi(v).y$ . Since $\phi(u)\prec_{DL}s^{\prime}$ , we have $s^{\prime}.y\leq\phi(u).y$ , and since $\phi(v)$ contains $\phi(u)$ , we have $\phi(u).y\in\phi(v).y$ . Since $\phi(v).y$ is an interval that starts at $-\infty$ , then $s^{\prime}.y\in\phi(v).y$ .
$\blacksquare$

$\max(s^{\prime}.x)\leq\max(\phi(v).x)$ . Similarly to the previous case, the implications give us the inequalities in $\max(s^{\prime}.x)\leq\max(\phi(u).x)\leq\max(\phi(v).x)$

Let $s^{\prime}\in S^{\prime}$ be an arbitrary segment. Since $\phi(v).y$ contains $s^{\prime}$ on the $y$ -axis, $\max(\phi(v).x)$ is larger than any point in $s^{\prime}$ on the $x$ -axis, then to show that $\phi(v)$ contains $s^{\prime}$ , it only remains to show that $\min(\phi(v).x)\leq\min(s^{\prime}.x)$ . Since $S^{\prime}$ was chosen to contain the segments in $\operatorname{\sf{succ}}^{DL}(\phi(u))$ with the largest $\min(s^{\prime}.x)$ , then $\min(\phi(v).x)\leq\min(s^{\prime}.x)$ holds for $s^{\prime}\in S^{\prime}$ , if it holds for any $k-1$ segments in $\operatorname{\sf{succ}}^{DL}(\phi(u))$ . Since $\{u,v\}$ is DL-bulky, $\phi(v)$ contains at least $k-1$ segments in $\operatorname{\sf{succ}}^{DL}(\phi(u))$ . This implies that $\phi(v)$ contains $S^{\prime}$ , and we have $U^{\prime}\in N_{G}(v)$ . Since this is true for all $v\in B$ , then $B$ and $U^{\prime}\cup\{u\}$ induce a $K_{k,k}$ , which is a contradiction.

The proof for DR-bulky edges is symmetric and the proof for C-bulky edges can easily be seen by selecting $S^{\prime}\subseteq\operatorname{\sf{succ}}^{C}(\phi(u))$ to be the $k-1$ segments $s^{\prime}\in S^{\prime}$ with the smallest $s^{\prime}.y$ . Since every $s^{\prime}\in S^{\prime}$ is already contained in $\phi(u)$ on the $x$ -axis, then the $y$ coordinate is the only factor determining which elements of $\operatorname{\sf{succ}}^{C}(\phi(u))$ are contained within a bottomless rectangle that contains $\phi(u)$ . $\hfill\blacktriangleleft$

Lemma 17.

For each $v\in V$ , there are at most $6(k-1)$ thin edges incident to $v$ .

Proof.

For a partial order ${\mathcal{P}}$ , we use $E({\mathcal{P}})$ to denote the number of comparable pairs in ${\mathcal{P}}$ .

Let $T\subset N_{G}(v)$ be the set of nodes $u$ , such that $\{u,v\}$ is thin. Let ${\mathcal{P}}_{l},{\mathcal{P}}_{r},{\mathcal{P}}_{c}$ be the partial orders ${\mathcal{P}}^{DL},{\mathcal{P}}^{DR},{\mathcal{P}}^{C}$ induced on set $\phi(T)$ . According to Observation 15, each pair of segments $s,s^{\prime}\in\phi(T)$ , is comparable in at least one of the partial orders. We then have $|E({\mathcal{P}}_{l})\cup E({\mathcal{P}}_{r})\cup E({\mathcal{P}}_{c})|\geq{|% T|\choose 2}$ .

Since for all $u\in T$ , the edge $\{u,v\}$ is thin, there are at most $(k-2)$ DL-successors of $\phi(u)$ in $\phi(T)$ , so we have $|E({\mathcal{P}}_{l})|\leq(k-2)|T|$ . Similarly, we have at most $(k-2)$ C-successors and $(k-2)$ DR-successors in $\phi(T)$ . Therefore, $|E({\mathcal{P}}_{r})|,|E({\mathcal{P}}_{c})|\leq(k-2)|T|$ . Combining the edges in the three partial orders, we get $|E({\mathcal{P}}_{l})\cup E({\mathcal{P}}_{r})\cup E({\mathcal{P}}_{c})|\leq 3% (k-2)|T|$ . Putting these inequalities together, we have

|T|(|T|-1)/2={|T|\choose 2}\leq 3(k-2)|T|

which implies that $|T|\leq 6k-11<6(k-1).$ $\hfill\blacktriangleleft$

Theorem 18.

For all $n,m,k\in\mathbb{N}$ , $Z_{\operatorname{\sf{CHAIN}}^{3}}(m,n;k,k)\leq(3m+6n)(k-1)$ .

Proof.

Let $G=(U\cup V,E)\in\operatorname{\sf{CHAIN}}^{3}$ be a $K_{k,k}$ -free graph, where $|U|=m$ , $|V|=n$ . Note that we defined every edge in $E$ as either thin or bulky. According to Lemma 16, the number of bulky edges in $E$ is at most $3(k-1)m$ . According to Lemma 17, the number of thin edges in $E$ is at most $6(k-1)n$ . This means that the total number of edges is $|E|\leq(3m+6n)(k-1)$ . $\hfill\blacktriangleleft$

Corollary 19.

When $m=n$ , we have $Z_{\operatorname{\sf{CHAIN}}^{3}}(n;k)\leq 9(k-1)n$ .

Theorem 1 (Dichotomy theorem). [Restated, see original statement.]

The following dichotomy results hold for all $k\in\mathbb{N}$ :

$\blacksquare$

$Z_{\operatorname{\sf{CHAIN}}^{3}}(n;k)\leq 9n(k-1)$ .
$\blacksquare$

$Z_{\operatorname{\sf{CHAIN}}^{4}}(n;k)\in\Omega(nk\cdot\frac{\log n}{\log\log n})$ .

Proof.

The first part will be proved in Section 4. The second part is a simple corollary of existing results: Chazelle [9] constructed $K_{2,2}$ -free $\operatorname{\sf{PRIG}}$ graphs on $n^{\prime}$ vertices that have at least $\Omega(n^{\prime}\cdot\frac{\log n^{\prime}}{\log\log n^{\prime}})$ edges. Chan and Har-Peled [4] assert the applicability of this result in graph theory, since the original context was pointer machines. By a simple modification that we show in Lemma 36, there exist $K_{k,k}$ -free $\operatorname{\sf{PRIG}}$ graphs on $N$ vertices with at least $\Omega(N\cdot(k-1)\cdot\frac{\log\frac{N}{k-1}}{\log\log\frac{N}{k-1}})=\Omega% (N\cdot k\cdot\frac{\log N}{\log\log N})$ edges. Since $\operatorname{\sf{PRIG}}\subseteq\operatorname{\sf{CONV}}^{2}$ (Lemma 31), which is contained in $\operatorname{\sf{CHAIN}}^{4}$ [7], then the constructed graphs give a lower bound for Zarankiewicz numbers for $\operatorname{\sf{CHAIN}}^{4}$ graphs. $\hfill\blacktriangleleft$

5 Grid Intersection Graphs

This section will use a more formal definition of grid intersection graphs. We say that $(\mathbf{X},\mathbf{Y},\phi)$ is a grid intersection representation of a bipartite graph $G=(U\cup V,E)$ , if $\mathbf{X}$ , $\mathbf{Y}$ are sets of horizontal and vertical segments in $\mathbb{R}^{2}$ respectively, $\phi:U\mapsto\mathbf{X},V\mapsto\mathbf{Y}$ , and for all $u\in U$ , $v\in V$ , we have $\{u,v\}\in E$ if and only if $\phi(u)$ and $\phi(v)$ intersect. A bipartite graph $G$ is a grid intersection graph ( $\operatorname{\sf{GIG}}$ ) if it has a grid intersection representation. For a segment $z\in\mathbf{X}\cup\mathbf{Y}$ , let $N(z)=\{z^{\prime}\in\mathbf{X}\cup\mathbf{Y}:z^{\prime}\cap z\neq\emptyset\}$ , e.g the set of segments that intersect $z$ .

Let $k$ be the minimum positive integer such that $G$ does not have $K_{k,k}$ as a subgraph.

Observation 20.

If $G=(U\cup V,E)\in\operatorname{\sf{GIG}}$ is $27(k-1)$ -degenerate, then $|E|\leq 27(k-1)(|U|+|V|)$ .

The proof is done via charging arguments.

5.1 Charging Arguments

For each segment $z\in\mathbf{X}\cup\mathbf{Y}$ , let $z . x$ and $z . y$ denote its projections to the $x$ -axis (horizontal) and $y$ -axis (vertical) respectively. Note that the projections are closed intervals and points. For an interval $[a,b]$ , let $\min([a,b])=a$ and $\max([a,b])=b$ . For two intervals $I$ and $I^{\prime}$ , we say that $I<I^{\prime}$ , if $\max(I)<\min(I^{\prime})$ .

For any segment $z\in\mathbf{X}\cup\mathbf{Y}$ , we define $\operatorname{DIR}_{down}(z)=\{z^{\prime}\in\mathbf{X}\cup\mathbf{Y}:z^{\prime% }.y<z.y\}$ , i.e. the set of segments whose projection to the $y$ axis is entirely smaller than that of $z$ . Similarly, we define $\operatorname{DIR}_{up}(z)=\{z^{\prime}\in\mathbf{X}\cup\mathbf{Y}:z^{\prime}.% y>z.y\}$ , $\operatorname{DIR}_{left}(z)=\{z^{\prime}\in\mathbf{X}\cup\mathbf{Y}:z^{\prime% }.x<z.x\}$ , $\operatorname{DIR}_{right}(z)=\{z^{\prime}\in\mathbf{X}\cup\mathbf{Y}:z^{% \prime}.x>z.x\}$ . For a set $S$ , we define $\operatorname{DIR}_{up}(S)=\bigcap_{z\in S}\operatorname{DIR}_{up}(z)$ and similarly for the other directions.

Definition 21.

We say that a vertical segment $\nu\in\mathbf{Y}$ is down-heavy with respect to $\sigma\in\mathbf{X}$ , if $\sigma.y\subset\nu.y$ and $|N(\nu)\cap\operatorname{DIR}_{down}(\sigma)|\geq 3(k-1)$ .

Definition 22.

We say that a vertical segment $\nu\in\mathbf{Y}$ is up-heavy with respect to $\sigma\in\mathbf{X}$ , if $\sigma.y\subset\nu.y$ and $|N(\nu)\cap\operatorname{DIR}_{up}(\sigma)|\geq 3(k-1)$ .

To show that a node $w\in U\cup V$ , such that $|N(w)|\leq 27(k-1)$ exists in any $\operatorname{\sf{GIG}}$ graph, we present a payment scheme algorithm whereby each horizontal segment starts with $27(k-1)$ credits, which is subsequently paid to vertical segments. We will see that each vertical segment $\nu\in\mathbf{Y}$ whose degree is at least $27(k-1)$ , receives at least $|N(\nu)|$ credits.

Algorithm 1 Neighbor payments.

Algorithm 2 Further payments.

Now, we will analyze the credits received by an arbitrary vertical segment $\nu\in\mathbf{Y}$ .

For a set of horizontal segments $S\subseteq\mathbf{X}$ , let $S . y$ denote the interval $[min,max]$ , where $min=\min_{\sigma\in S}(\sigma.y)$ and $max=\max_{\sigma\in S}(\sigma.y)$ .

Lemma 23.

Let $S\subset N(\nu)$ , such that

$\blacksquare$

$|S|=3(k-1)$
$\blacksquare$

$|N(\nu)\cap\operatorname{DIR}_{up}(S)|\geq 3(k-1)$ (Intuition: $S$ is not among the highest elements of $N(\nu)$ )
$\blacksquare$

$|N(\nu)\cap\operatorname{DIR}_{down}(S)|\geq 3(k-1)$ (Intuition: $S$ is not among the lowest elements of $N(\nu)$ )

Then at least $\frac{9}{2}(k-1)$ credits are paid to $\nu$ from horizontal segments $\sigma\in\mathbf{X}$ , such that $\sigma.y\in S.y$ .

The proof is deferred to Appendix D.

Lemma 24.

If $|N(\nu)|\geq 27(k-1)$ , then $\nu$ receives at least $|N(\nu)|$ credits.

Proof.

We choose the maximum number $\ell$ of disjoint sets $S_{1},\ldots S_{\ell}$ in $N(\nu)$ , such that every set $S_{i}$ satisfies the conditions of Lemma 23. Since each set receives $\frac{9}{2}(k-1)$ credits from a distinct set of horizontal segments, then the total amount in credits $\nu$ receives is at least $\frac{9}{2}(k-1)\ell$ .

It remains to see that $\frac{9}{2}(k-1)\ell\geq|N(\nu)|$ . Note that $\ell\geq\lfloor\frac{|N(\nu)|-3(k-1)-3(k-1)}{3(k-1)}\rfloor\geq\frac{|N(\nu)|-% 9(k-1)}{3(k-1)}$ . We get that $\frac{9}{2}(k-1)\ell\geq\frac{9}{2}(k-1)\frac{|N(\nu)|-9(k-1)}{3(k-1)}=\frac{3% }{2}|N(\nu)|-\frac{27}{2}(k-1)=|N(\nu)|+\frac{1}{2}(|N(\nu)|-27(k-1))$ . Since according to our assumption $|N(\nu)|\geq 27(k-1)$ , then this result is at least $|N(\nu)|$ . $\hfill\blacktriangleleft$

Lemma 25.

Any $G=(U\cup V,E)\in\operatorname{\sf{GIG}}$ is $27(k-1)$ -degenerate.

Proof.

Assume by contradiction that there is a graph $G=(U\cup V,E)\in\operatorname{\sf{GIG}}$ , where no such node exists. Since according to our assumption, for any node $w\in U\cup V$ , we have $|N(w)|\geq 27(k-1)+1$ , then by running Algorithm 1 and Algorithm 2, we see that for each horizontal node, fewer credits are given out than their degree. This implies that the amount in credits given by these algorithms is smaller than $|E|$ .

For each vertical node $\nu\in\mathbf{Y}$ , on the other hand, according to Lemma 24, the amount in credits received is at least that of their degree. This implies that the total amount in credits received from these algorithms greater than or equal to $|E|$ . This is a contradiction. $\hfill\blacktriangleleft$

Theorem 26.

For all $n,m,k\in\mathbb{N}$ , $Z_{\operatorname{\sf{GIG}}}(m,n;k,k)\leq 27(m+n)(k-1)$ .

Proof.

The result follows from Lemma 25 and Observation 7. $\hfill\blacktriangleleft$

Theorem 3. [Restated, see original statement.]

For all $k,n\in\mathbb{N}$ , $Z_{\operatorname{\sf{GIG}}}(n;k)\leq 54n(k-1)$ .

Proof.

The result follows from Theorem 26, when $n=m$ $\hfill\blacktriangleleft$

References

[1] Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Teresa M. Przytycka, and Sue Whitesides. Grid intersection graphs and boxicity. Discret. Math., 114(1-3):41–49, 1993. doi:10.1016/0012-365X(93)90354-V.
[2] Tom Bohman and Peter Keevash. The early evolution of the H-free process. Inventiones Mathematicae, 181(2):291–336, May 2010. doi:10.1007/s00222-010-0247-x.
[3] Romain Bourneuf, Matija Bucić, Linda Cook, and James Davies. On polynomial degree-boundedness. Advances in Combinatorics, 2024. doi:10.19086/aic.2024.5.
[4] Timothy M. Chan and Sariel Har-Peled. On the number of incidences when avoiding an induced biclique in geometric settings. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 1398–1413. SIAM, 2023. doi:10.1137/1.9781611977554.CH50.
[5] Timothy M. Chan, Chaya Keller, and Shakhar Smorodinsky. On Zarankiewicz’s problem for intersection hypergraphs of geometric objects. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazawa, Japan, volume 332 of LIPIcs, pages 33:1–33:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPICS.SOCG.2025.33.
[6] L. Sunil Chandran, Mathew C. Francis, and Rogers Mathew. Chordal bipartite graphs with high boxicity. Graphs Comb., 27(3):353–362, 2011. doi:10.1007/S00373-011-1017-2.
[7] Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, and Ryuhei Uehara. Intersection dimension of bipartite graphs. In T. V. Gopal, Manindra Agrawal, Angsheng Li, and S. Barry Cooper, editors, Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings, volume 8402 of Lecture Notes in Computer Science, pages 323–340. Springer, 2014. doi:10.1007/978-3-319-06089-7_23.
[8] Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, and Ryuhei Uehara. Ferrers dimension of grid intersection graphs. Discret. Appl. Math., 216:130–135, 2017. doi:10.1016/J.DAM.2015.05.035.
[9] Bernard Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. J. ACM, 37(2):200–212, 1990. doi:10.1145/77600.77614.
[10] Thao Do. Representation complexities of semialgebraic graphs. SIAM J. Discret. Math., 33(4):1864–1877, 2019. doi:10.1137/18M1221606.
[11] Martin Farber. Characterizations of strongly chordal graphs. Discret. Math., 43(2-3):173–189, 1983. doi:10.1016/0012-365X(83)90154-1.
[12] Jacob Fox and János Pach. Separator theorems and Turán-type results for planar intersection graphs. Advances in Mathematics, 219(3):1070–1080, 2008. doi:10.1016/j.aim.2008.06.002.
[13] Jacob Fox and János Pach. A separator theorem for string graphs and its applications. Comb. Probab. Comput., 19(3):371–390, 2010. doi:10.1017/S0963548309990459.
[14] Jacob Fox, János Pach, Adam Sheffer, Andrew Suk, and Joshua Zahl. A semi-algebraic version of Zarankiewicz’s problem. Journal of the European Mathematical Society (EMS Publishing), 19(6):1785–1810, 2017. doi:10.4171/JEMS/705.
[15] Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, and Yngve Villanger. Enumerating minimal dominating sets in chordal bipartite graphs. Discret. Appl. Math., 199:30–36, 2016. doi:10.1016/J.DAM.2014.12.010.
[16] Irith Ben-Arroyo Hartman, Ilan Newman, and Ran Ziv. On grid intersection graphs. Discret. Math., 87(1):41–52, 1991. doi:10.1016/0012-365X(91)90069-E.
[17] Oliver Janzer and Cosmin Pohoata. On the Zarankiewicz problem for graphs with bounded VC-dimension. Comb., 44(4):839–848, 2024. doi:10.1007/S00493-024-00095-2.
[18] Chaya Keller and Shakhar Smorodinsky. Zarankiewicz’s problem via $\epsilon$ -t-nets. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 66:1–66:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.66.
[19] Bettina Klinz, Rüdiger Rudolf, and Gerhard J. Woeginger. Permuting matrices to avoid forbidden submatrices. Discret. Appl. Math., 60(1-3):223–248, 1995. doi:10.1016/0166-218X(94)00054-H.
[20] Tamás Kővári, Vera T. Sós, and Pál Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicum, 3:50–57, 1954. URL: http://eudml.org/doc/210011.
[21] Jan Kratochvíl. A special planar satisfiability problem and a consequence of its NP-completeness. Discret. Appl. Math., 52(3):233–252, 1994. doi:10.1016/0166-218X(94)90143-0.
[22] Jan Kratochvíl and Jiří Matoušek. NP-hardness results for intersection graphs. Commentationes Mathematicae Universitatis Carolinae, 30(4):761–773, 1989. URL: http://eudml.org/doc/17790.
[23] Anna Lubiw. Doubly lexical orderings of matrices. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 396–404. ACM, 1985. doi:10.1145/22145.22189.
[24] Haiko Müller. Hamiltonian circuits in chordal bipartite graphs. Discret. Math., 156(1-3):291–298, 1996. doi:10.1016/0012-365X(95)00057-4.
[25] Nabil H. Mustafa and János Pach. On the Zarankiewicz problem for intersection hypergraphs. In Emilio Di Giacomo and Anna Lubiw, editors, Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, volume 9411 of Lecture Notes in Computer Science, pages 207–216. Springer, 2015. doi:10.1007/978-3-319-27261-0_18.
[26] Irina Mustata. On subclasses of grid intersection graphs. PhD thesis, Technische Universität Berlin, 2014. doi:10.14279/depositonce-4202.
[27] Pranab K. Saha, Asim Basu, Malay K. Sen, and Douglas B. West. Permutation bigraphs and interval containments. Discret. Appl. Math., 175:71–78, 2014. doi:10.1016/J.DAM.2014.05.020.
[28] Shakhar Smorodinsky. A survey of Zarankiewicz problem in geometry. CoRR, abs/2410.03702, 2024. doi:10.48550/arXiv.2410.03702.
[29] István Tomon and Dmitriy Zakharov. Turán-type results for intersection graphs of boxes. Combinatorics, Probability and Computing, 30(6):982–987, 2021. doi:10.1017/S0963548321000171.
[30] Ryuhei Uehara, Seinosuke Toda, and Takayuki Nagoya. Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs. Discret. Appl. Math., 145(3):479–482, 2005. doi:10.1016/J.DAM.2004.06.008.

Appendix A Higher Ferrers Dimension

We prove Corollary 2 in this section. Note that the proof closely follows Section 2.2 of Chan and Har-Peled [4]. We repeat their definitions here for completeness. For integers $a\leq b$ , we denote $\{a,a+1,\ldots,b\}$ by $[[a:b]]$ . A dyadic range is an integer range of the form $[[s2^{i}:(s+1)2^{i+1}-1]]$ for some integers $s$ and $i$ . Considering a $\operatorname{\sf{CHAIN}}$ graph, we can view the points as integers ${\mathcal{P}}=\{1,\ldots,n\}$ . Denote by ${\mathcal{D}}(n)$ the set of all dyadic ranges. Each integer (point) appears in at most $\lceil\log n\rceil$ dyadic ranges.

Notice that a ray is simply a range $[[a,n]]$ for some $a$ .

Lemma 27 (An analogue of Lemma 2.2 in [4]).

Let $r$ be a ray. Denote by $\sf{dy}(r)$ the set of minimal disjoint dyadic ranges covering $r$ . Then $\sf{dy}(r)$ is unique and contains at most $\lceil\log n\rceil$ ranges.

Remark that we have $\lceil\log n\rceil$ instead of $2\lceil\log n\rceil$ as in [4] since we have rays instead of intervals. The following lemma implies Corollary 2.

Lemma 28.

Let $G=(A\cup B,E)\in\operatorname{\sf{CHAIN}}^{d}$ for $d\geq 3$ that does not contain $K_{k,k}$ . Then the number of edges in $G$ is at most $O(|A|+|B|)\cdot k\cdot\lceil\log n\rceil^{d-3}$ where $n=\max\{|A|,|B|\}$ .

Proof.

The proof is obtained by induction on $d$ . The base case when $d=3$ is proved in Theorem 18. When $d>3$ , assume the claim is true for all dimensions up to $d-1$ . We write $G=G^{\prime}\cap\widehat{G}$ where $G^{\prime}\in\operatorname{\sf{CHAIN}}$ and $\widehat{G}\in\operatorname{\sf{CHAIN}}^{d-1}$ . Since $G^{\prime}\in\operatorname{\sf{CHAIN}}$ , it is an intersection bigraph of rays ${\mathcal{R}}$ and points ${\mathcal{P}}$ where $a\in A$ is mapped to $r_{a}\in{\mathcal{R}}$ and $b\in B$ to $p_{b}\in{\mathcal{P}}$ . Assume w.l.o.g. that ${\mathcal{P}}=\{1,\ldots,q\}$ for $q\leq n$ .

For each dyadic range $\nu\in{\mathcal{D}}(q)$ , we have an auxiliary graph $G_{\nu}$ which is an induced subgraph $G[A_{\nu}\cup B_{\nu}]$ where $A_{\nu}=\{a\in A:\nu\in\sf{dy}(r_{a})\}$ and $B_{\nu}=\{b:p_{b}\in\nu\}$ . Notice that $|E(G)|\leq\sum_{\nu\in{\mathcal{D}}(n)}|E(G_{\nu})|$ .

Moreover, $G_{\nu}=G^{\prime}[A_{\nu}\cup B_{\nu}]\cap\widehat{G}[A_{\nu}\cup B_{\nu}]$ where $G^{\prime}[A_{\nu}\cup B_{\nu}]$ is a biclique; therefore $G_{\nu}\in\operatorname{\sf{CHAIN}}^{d-1}$ and is free of $k$ -by- $k$ biclique. This allows us to invoke the induction hypothesis, which implies that

|E(G)|\leq\sum_{\nu\in{\mathcal{D}}(n)}O(|A_{\nu}|+|B_{\nu}|)k\lceil\log n% \rceil^{d-4}

Finally, since each vertex $a\in A$ appears in at most $\lceil\log q\rceil\leq\lceil\log n\rceil$ sets $A_{\nu}$ (and similarly for each vertex $b\in B$ ), this implies that the above sum is at most $O(|A|+|B|)k\lceil\log n\rceil^{d-3}$ . $\hfill\blacktriangleleft$

Appendix B Intersection of Two Convex Graphs

In this section, we will use a more formal definition of $\operatorname{\sf{PRIG}}$ graphs. We say that $(\mathbf{X},\mathbf{Y},\phi)$ is a point-rectangle intersection representation of a graph $G=(U\cup V,E)$ , if $\mathbf{X}$ , $\mathbf{Y}$ are sets of points and rectangles, respectively, in $\mathbb{R}^{2}$ , $\phi:U\mapsto\mathbf{X},V\mapsto\mathbf{Y}$ , and for all $u\in U$ , $v\in V$ , we have $\{u,v\}\in E$ if and only if $\phi(u)$ and $\phi(v)$ intersect. A graph $G=(U\cup V,E)$ is a point-rectangle intersection bigraph, if it has a point-rectangle intersection representation. We call the class of such graphs $\operatorname{\sf{PRIG}}$ .

Lemma 29.

Any graph $G=(U\cup V,E)\in\operatorname{\sf{CONV}}^{2}$ is a disjoint union of $\operatorname{\sf{GIG}}$ and $\operatorname{\sf{PRIG}}$ graphs.

Proof.

Since $G\in\operatorname{\sf{CONV}}^{2}$ , then there exist graphs $G_{1}$ and $G_{2}$ , such that $G_{1}\cap G_{2}=G$ . Let $V_{1}$ and $V_{2}$ be the partitions that the graphs $G_{1}$ and $G_{2}$ , respectively, are convex over, and $U_{1}\subseteq V(G_{1})$ , $U_{2}\subseteq V(G_{2})$ , the other partitions.

Since $\operatorname{\sf{CONV}}$ graphs are closed under taking induced subgraphs, we can assume that $U_{1}\cup V_{1}=U_{2}\cup V_{2}$ . Let $A_{1}=U_{1}\cap U_{2}$ , $A_{2}=U_{1}\cap V_{2}$ , $B_{1}=V_{1}\cap V_{2}$ , $B_{2}=V_{1}\cap U_{2}$ , as shown on Figure 9.

We have $U\cup V=A_{1}\cup A_{2}\cup B_{1}\cup B_{2}$ and all edges must start and end at these nodes. Since $A_{1}$ is in the same partition as $A_{2}$ , and $B_{2}$ , in at least one of the graphs, there can be no edges between $A_{1}$ and $A_{2}\cup B_{2}$ . The same is true for $B_{1}$ . Clearly, $G$ can have one component consisting of nodes $A_{1}\cup B_{1}$ and another component consisting of nodes $A_{2}\cup B_{2}$ , with no edges between these components.

It remains to see that $G[A_{1}\cup B_{1}]\in\operatorname{\sf{PRIG}}$ and $G[A_{2}\cup B_{2}]\in\operatorname{\sf{GIG}}$ . To do this, we show that there exist representations of these graphs in $\operatorname{\sf{PRIG}}$ and $\operatorname{\sf{GIG}}$ respectively, such that the projections of these representations to $x$ and $y$ axis are the convex representations of graphs $G_{1}$ and $G_{2}$ induced on $A_{1}\cup B_{1}$ and $A_{2}\cup B_{2}$ respectively.

Let $H_{1}=G_{1}[A_{1}\cup B_{1}]$ and $H_{2}=G_{2}[A_{1}\cup B_{1}]$ . Since $G_{1}$ and $G_{2}$ are convex over $V_{1}$ and $V_{2}$ , and $B_{1}=V_{1}\cap V_{2}$ , then $H_{1}$ and $H_{2}$ are convex over $B_{1}$ . Let $(\mathbf{X}_{1},\mathbf{Y}_{1},\phi_{1})$ be the point-segment representation of $H_{1}$ , such that $\mathbf{Y}_{1}$ are the points. Then $\phi_{1}:A_{1}\mapsto\mathbf{X}_{1},B_{1}\mapsto\mathbf{Y}_{1}$ . Let $(\mathbf{X}_{2},\mathbf{Y}_{2},\phi_{2})$ be the point-segment representation of $H_{2}$ , such that $\mathbf{Y}_{2}$ are the points. Then $\phi_{2}:A_{1}\mapsto\mathbf{X}_{2},B_{1}\mapsto\mathbf{Y}_{2}$ . We construct a mapping $\phi:A_{1}\mapsto\mathbf{X},B_{1}\mapsto\mathbf{Y}$ , where $\mathbf{X}$ is a set of rectangles, and $\mathbf{Y}$ a set of points in $\mathbb{R}^{2}$ . For each $w\in A_{1}\cup B_{1}$ , $\phi(w)$ is the object whose projection to the $x$ -axis is $\phi_{1}(w)$ and whose projection to the $y$ -axis is $\phi_{2}(w)$ . Note that for all $a\in A_{1}$ , $\phi(a)$ is a rectangle, and for all $b\in B_{1}$ , $\phi(b)$ is a point. It is easy to verify that $\phi(a)$ intersects $\phi(b)$ , if and only if $\phi_{1}(a)$ intersects $\phi_{1}(b)$ and $\phi_{2}(a)$ intersects $\phi_{2}(b)$ , which implies that there is an edge $\{a,b\}$ in the graph represented by $\phi$ , if and only if $\{a,b\}\in E(H_{1})\cap E(H_{2})$ . This means that $(\mathbf{X},\mathbf{Y},\phi)$ is a valid representation of $G[A_{1}\cup B_{1}]\in\operatorname{\sf{PRIG}}$ .

Showing that $G[A_{2}\cup B_{2}]\in\operatorname{\sf{GIG}}$ is similar, but not quite symmetric. Let $H_{1}=G_{1}[A_{2}\cup B_{2}]$ and $H_{2}=G_{2}[A_{2}\cup B_{2}]$ . Since $G_{1}$ and $G_{2}$ are convex over $V_{1}$ and $V_{2}$ , and $A_{2}\subseteq V_{2}$ , $B_{2}\subseteq V_{1}$ , then $H_{1}$ and $H_{2}$ are convex over $A_{2}$ and $B_{2}$ respectively. Let us define $(\mathbf{X}_{1},\mathbf{Y}_{1},\phi_{1})$ to be the point-segment representation of $H_{1}$ , such that $\mathbf{X}_{1}$ are the points. Then $\phi_{1}:A_{2}\mapsto\mathbf{X}_{1},B_{2}\mapsto\mathbf{Y}_{1}$ . Let $(\mathbf{X}_{2},\mathbf{Y}_{2},\phi_{2})$ be the point-segment representation of $H_{2}$ , such that $\mathbf{Y}_{2}$ are the points. Then $\phi_{2}:A_{2}\mapsto\mathbf{X}_{2},B_{2}\mapsto\mathbf{Y}_{2}$ . We construct a mapping $\phi:A_{2}\mapsto\mathbf{X},B_{2}\mapsto\mathbf{Y}$ , where $\mathbf{X}$ is a set of horizontal segments, and $\mathbf{Y}$ is a set of vertical segments in $\mathbb{R}^{2}$ . For each $w\in A_{2}\cup B_{2}$ , $\phi(w)$ is the object whose projection to the $y$ -axis is $\phi_{1}(w)$ and whose projection to the $x$ -axis is $\phi_{2}(w)$ . Note that for all $a\in A_{2}$ , $\phi(a)$ is a horizontal segment and for all $b\in B_{1}$ , $\phi(b)$ is a vertical segment. It is easy to verify that $\phi(a)$ intersects $\phi(b)$ , if and only if $\phi_{1}(a)$ intersects $\phi_{1}(b)$ and $\phi_{2}(a)$ intersects $\phi_{2}(b)$ , which implies that there is an edge $\{a,b\}$ in the graph represented by $\phi$ , if and only if $\{a,b\}\in E(H_{1})\cap E(H_{2})$ . This means that $(\mathbf{X},\mathbf{Y},\phi)$ is a valid representation of $G[A_{1}\cup B_{1}]\in\operatorname{\sf{GIG}}$ . $\hfill\blacktriangleleft$

For graphs $G_{1}$ , $G_{2}$ , let $G_{1}\mathbin{\dot{\cup}}G_{2}$ to denote the disjoint union of $G_{1}$ and $G_{2}$ .

Lemma 30.

$\operatorname{\sf{CONV}}^{2}$ is closed under disjoint union.

Proof.

Let $G$ , $G^{\prime}$ be any disjoint graphs in $\operatorname{\sf{CONV}}^{2}$ . Then we have graphs $G_{1},G_{2}\in\operatorname{\sf{CONV}}$ , such that $G_{1}\cap G_{2}=G$ , and graphs $G^{\prime}_{1},G^{\prime}_{2}\in\operatorname{\sf{CONV}}$ , such that $G^{\prime}_{1}\cap G^{\prime}_{2}=G^{\prime}$ . Since $\operatorname{\sf{CONV}}$ is closed under disjoint union, then $G_{1}\mathbin{\dot{\cup}}G^{\prime}_{1}\in\operatorname{\sf{CONV}}$ and $G_{2}\mathbin{\dot{\cup}}G^{\prime}_{2}\in\operatorname{\sf{CONV}}$ . Then $(G_{1}\mathbin{\dot{\cup}}G^{\prime}_{1})\cap(G_{2}\mathbin{\dot{\cup}}G^{% \prime}_{2})\in\operatorname{\sf{CONV}}^{2}$ . Since $G_{1}$ only shares vertices with $G_{2}$ , and similarly, $G^{\prime}_{1}$ only shares vertices with $G^{\prime}_{2}$ , then $(G_{1}\mathbin{\dot{\cup}}G^{\prime}_{1})\cap(G_{2}\mathbin{\dot{\cup}}G^{% \prime}_{2})=(G_{1}\cap G_{2})\mathbin{\dot{\cup}}(G^{\prime}_{1}\cap G^{% \prime}_{2})=G\mathbin{\dot{\cup}}G^{\prime}\in\operatorname{\sf{CONV}}^{2}$ . $\hfill\blacktriangleleft$

Lemma 31.

$\operatorname{\sf{PRIG}}\subseteq\operatorname{\sf{CONV}}^{2}$ .

Proof.

Let $G=(U\cup V,E)$ be any graph in $\operatorname{\sf{PRIG}}$ , and $(\mathbf{X},\mathbf{Y},\phi)$ the representation of $G$ in $\operatorname{\sf{PRIG}}$ , such that $\mathbf{X}$ is a set of points and $\mathbf{Y}$ a set of rectangles in $\mathbb{R}^{2}$ . Then we can construct mappings $\phi_{1}$ and $\phi_{2}$ , such that for all $w\in V(G)$ , $\phi_{1}(w)$ and $\phi_{2}(w)$ are the projections of $\phi(w)$ to $x$ and $y$ axis respectively. Let $G_{1}$ and $G_{2}$ be the graphs represented by $\phi_{1}(w)$ and $\phi_{2}(w)$ respectively. Since $\phi_{1}(w)$ maps the vertices $V(G)$ to points and segments based on their partitions, then $G_{1}\in\operatorname{\sf{CONV}}$ . Similarly for $G_{2}$ . Since for any $u\in U$ , $v\in V$ , we have that $\phi(u)$ intersects $\phi(v)$ if and only if $\phi_{1}(u)$ intersects $\phi_{1}(v)$ and $\phi_{2}(u)$ intersects $\phi_{2}(v)$ , then $G_{1}\cap G_{2}=G$ . This proves that $G\in\operatorname{\sf{CONV}}^{2}$ . $\hfill\blacktriangleleft$

Lemma 32.

$\operatorname{\sf{GIG}}\subseteq\operatorname{\sf{CONV}}^{2}$ .

Proof.

The proof is symmetric to Lemma 31. $\hfill\blacktriangleleft$

Theorem 6: Any graph $G=(U\cup V,E)\in\operatorname{\sf{CONV}}^{2}$ if and only if it is a disjoint union of $\operatorname{\sf{GIG}}$ and $\operatorname{\sf{PRIG}}$ graphs.

This follows from Lemma 29, Lemma 30, Lemma 31, and Lemma 32.

Appendix C Segment Bottomless Rectangle Containment Bigraph

We say that $(\mathbf{X},\mathbf{Y},\phi)$ is an interval containment representation of a graph $G=(U\cup V,E)$ , if $\mathbf{X}$ , $\mathbf{Y}$ in $\mathbb{R}$ are intervals, $\phi:U\mapsto\mathbf{X},V\mapsto\mathbf{Y}$ , and for all $u\in U$ , $v\in V$ , we have $\{u,v\}\in E$ if and only if $\phi(u)$ is contained within $\phi(v)$ . A graph $G$ is an interval containment bigraph, if it has an interval containment representation. According to [7], the class of interval containment bigraphs is $\operatorname{\sf{CHAIN}}^{2}$ .

Proposition 33.

If a graph $G=(U\cup V,E)\in\operatorname{\sf{CHAIN}}$ has a point ray representation $(\mathbf{X},\mathbf{Y},\phi)$ , $\phi:U\mapsto\mathbf{X},V\mapsto\mathbf{Y}$ , then it also has a point ray representation $(\mathbf{X}^{\prime},\mathbf{Y}^{\prime},\phi^{\prime})$ , $\phi^{\prime}:V\mapsto\mathbf{X}^{\prime},U\mapsto\mathbf{Y}^{\prime}$ , where $\mathbf{X},\mathbf{X}^{\prime}$ are points and $\mathbf{Y},\mathbf{Y}^{\prime}$ are rays.

Proof.

We are given $G=(U\cup V,E)\in\operatorname{\sf{CHAIN}}$ with a point ray representation $(\mathbf{X},\mathbf{Y},\phi)$ , $\phi:U\mapsto\mathbf{X},V\mapsto\mathbf{Y}$ , where $\mathbf{X}$ represents points and $\mathbf{Y}$ represents rays extending to $\infty$ in $\mathbb{R}$ .

For $\nu\in\mathbf{Y}$ , let $\nu.p$ denote the minimum point in ray $\nu$ . Then for all $u\in U$ , $v\in V$ , we say that $\phi(v).p<\phi(u)$ , if and only if $\{u,v\}\in E$ .

We construct $(\mathbf{X}^{\prime},\mathbf{Y}^{\prime},\phi^{\prime})$ such that for each $u\in U$ , $\phi^{\prime}(u)=(-\infty,\phi(u)]$ , $\phi^{\prime}(v)=\phi(v).p$ . Then for all $u\in U$ , $v\in V$ , $\phi^{\prime}(u)$ and $phi^{\prime}(v)$ intersect if $\phi^{\prime}(v)<\phi^{\prime}(u).p$ , which happens if and only if $\phi(v).p<\phi(u)$ . This implies that $(\mathbf{X}^{\prime},\mathbf{Y}^{\prime},\phi^{\prime})$ is a representation of $G$ , where the partition $U$ is mapped to rays and $V$ to points. By flipping the representation, it is easy to see that there is an equivalent representation where rays extend to $\infty$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Lemma 14. A graph $G$ is of Ferrers dimension three ( $G\in\operatorname{\sf{CHAIN}}^{3}$ ) if and only if it is a bottomless rectangle segment containment graph.

Proof.

Let $({\mathcal{S}},{\mathcal{B}},\phi)$ be a segment bottomless rectangle representation of graph $G=(U\cup V,E)$ , such that $\phi:U\mapsto{\mathcal{S}},V\mapsto{\mathcal{B}}$ . We will see that $G\in\operatorname{\sf{CHAIN}}^{3}$ .

First, we consider the graph $G_{x}=(U\cup V,E_{x})$ represented by the projections of ${\mathcal{S}},{\mathcal{B}}$ to the $x$ axis. Since $G_{x}$ is an interval containment bigraph, then $G_{x}\in\operatorname{\sf{CHAIN}}^{2}$ ([27], [7]). Secondly, consider the graph $G_{y}=(U\cup V,E_{y})$ represented by the projections of ${\mathcal{S}},{\mathcal{B}}$ to the $y$ axis. Since $G_{y}$ is an intersection graph of points and rays, then $G_{y}\in\operatorname{\sf{CHAIN}}$ . Since each $b\in{\mathcal{B}}$ contains $s\in{\mathcal{S}}$ if and only if $s.x\subseteq b.x$ and $s.y\subseteq b.y$ , then $G=G_{x}\cap G_{y}\in\operatorname{\sf{CHAIN}}^{2}\cdot\operatorname{\sf{CHAIN}% }=\operatorname{\sf{CHAIN}}^{3}$ .

Next, we will show that any graph $G=(U\cup V,E)\in\operatorname{\sf{CHAIN}}^{3}$ has a segment bottomless rectangle representation. According to [7], there exist graphs $G_{x}=(U\cup V,E_{x})\in\operatorname{\sf{CHAIN}}^{2}$ and $G_{y}=(U\cup V,E_{y})\in\operatorname{\sf{CHAIN}}$ , such that $G_{x}\cap G_{y}=G$ . Let $(\mathbf{X}_{x},\mathbf{Y}_{x},\phi_{x})$ be an interval containment representation of $G_{x}$ , such that $\mathbf{X}$ represent the contained segments and $\mathbf{Y}$ the containing ones. Let us consider the case that $\phi_{x}:U\mapsto\mathbf{X}_{x},V\mapsto\mathbf{Y}_{x}$ , the case that $\phi_{x}:V\mapsto\mathbf{X}_{x},U\mapsto\mathbf{Y}_{x}$ is symmetric. Let $(\mathbf{X}_{y},\mathbf{Y}_{y},\phi_{y})$ be a point ray representation of $G_{y}$ , such that $\mathbf{X}_{y}$ are points and $\mathbf{Y}_{y}$ are rays, $\phi_{y}:U\mapsto\mathbf{X}_{y},V\mapsto\mathbf{Y}_{y}$ (Proposition 33).

We construct a segment bottomless rectangle representation $({\mathcal{S}},{\mathcal{B}},\phi)$ , $\phi:U\mapsto{\mathcal{S}},V\mapsto{\mathcal{B}}$ , such that for all $w\in U\cup V$ , $\phi(w).x=\phi_{x}(w)$ , $\phi(w).y=\phi_{y}(w)$ . Let $G^{\prime}$ be the graph represented by $({\mathcal{S}},{\mathcal{B}},\phi)$ . For all $u\in U$ , $v\in V$ , $\phi(u)$ is contained within $\phi(v)$ if and only if $\phi_{x}(u)$ is contained within $\phi_{x}(v)$ and $\phi_{y}(u)$ is contained within $\phi_{y}(v)$ . This implies that $G^{\prime}=G_{x}\cap G_{y}$ , which means that $({\mathcal{S}},{\mathcal{B}},\phi)$ is a representation of $G$ . $\hfill\blacktriangleleft$

Appendix D Grid Intersection Graphs

We say $\sigma\in N(\nu)$ is generous to $\nu$ (or simply generous), if Algorithm 1 pays any credits to $\nu$ from $\sigma$ . We consider the remaining segments in $N(\nu)$ stingy to $\nu$ .

First, we will see that if for a section of a vertical node, not enough credits are gained from Algorithm 1, then there are horizontal segments in that section, which will contribute to Algorithm 2 instead.

Lemma 34.

Let $S\subseteq N(\nu)$ , and $S^{\prime}\subseteq S$ be the stingy subset, such that

$\blacksquare$

$|S|\geq 3(k-1)$
$\blacksquare$

$|S-S^{\prime}|\leq k-1$
$\blacksquare$

$N(\nu)\subseteq\operatorname{DIR}_{up}(S)\cup\operatorname{DIR}_{down}(S)\cup S$ ( $S$ contains consecutive neighbors of $\nu$ )

Then there exists a set $S^{*}\in\operatorname{DIR}_{right}(\nu)$ , such that

$\blacksquare$

$|S^{*}|\geq k-1$
$\blacksquare$

$S^{*}.y\subseteq S.y$
$\blacksquare$

$\bigcap_{\sigma\in S^{\prime}\cup S^{*}}\sigma.x\neq\emptyset$

Proof.

The number of stingy nodes is at least $2(k-1)$ . Let the stingy subset of $S$ be $S^{\prime}$ . For any $\sigma\in S^{\prime}$ , there are at least $k-1$ segments in either $\operatorname{DIR}_{up}(\sigma)\cap S^{\prime}$ or $\operatorname{DIR}_{down}(\sigma)\cap S^{\prime}$ .

Let $\sigma\in S^{\prime}$ be the segment with the smallest $\max(\sigma.x)$ . Let $\operatorname{DIR}_{down}(\sigma)\cap S^{\prime}=S^{\prime}_{down}$ and $\operatorname{DIR}_{up}(\sigma)\cap S^{\prime}=S^{\prime}_{up}$ . We consider the case that $|S^{\prime}_{down}|\geq k-1$ . The case that $|S^{\prime}_{up}|\geq k-1$ is symmetric. Let $Q$ be the $(k-1)$ rightmost down-heavy vertical segments in Algorithm 1, that are each paid $\frac{9}{2}$ credits from $\sigma$ . Let $\nu^{\prime}\in Q$ be the vertical segment with the largest $\min(\nu^{\prime}.y)$ .

Since $\nu^{\prime}\in Q$ has the largest $\min(\nu^{\prime}.y)$ and $\sigma\in S^{\prime}$ has the smallest $\max(\sigma.x)$ , then $\{\sigma\}\cup S^{\prime}_{down}\cap N(v^{\prime})$ and $Q\cup\{\nu\}$ induce a biclique (Figure 10). Since $|Q\cup\{\nu\}|=k$ and there cannot exist a $K_{k,k}$ , then $|S^{\prime}_{down}\cap N(v^{\prime})|\leq k-2$ , which implies that $\min(\nu^{\prime}.y)$ is greater than $\min(S.y)$ ( $\nu^{\prime}$ does not extend far enough down to include $k-1$ stingy nodes below $\sigma$ ).

Since $\nu^{\prime}$ is down-heavy w.r.t $\sigma$ , then $|N(\nu^{\prime})\cap\operatorname{DIR}_{down}(\sigma)|\geq 3(k-1)$ (Definition 21). Let $\Gamma=N(\nu^{\prime})\cap\operatorname{DIR}_{down}(\sigma)$ . Note that $\Gamma.y\subseteq S.y$ , because $\min(\nu^{\prime}.y)$ is greater than $\min(S.y)$ and $\max(\Gamma.y)<\sigma.y$ . Due to how $S$ was chosen (the last condition), this implies that the nodes in $\Gamma$ that intersect $\nu$ are in $S$ .

Since $(k-1)$ nodes of $S^{\prime}_{down}=\operatorname{DIR}_{down}(\sigma)\cap S^{\prime}$ cannot be in $N(\nu^{\prime})$ , then $|\Gamma\cap S^{\prime}|\leq k-2$ . Since $|S-S^{\prime}|\leq k-2$ , then $|\Gamma-S|\geq 3(k-1)-(k-2)-(k-2)=k+1$ .

Let us consider the conditions for $S^{*}=\Gamma-S$ . Since $\Gamma\in N(\nu^{\prime})$ , $\nu^{\prime}\in Q\subseteq\operatorname{DIR}_{right}(\nu)$ , and none of $\Gamma-S$ intersect $\nu$ , then $\Gamma-S\in\operatorname{DIR}_{right}(\nu)$ . We already saw that $|\Gamma-S|\geq k-1$ and $\Gamma.y\subseteq S.y$ . Since $\sigma\in S^{\prime}$ is the segment with the smallest $\max(\sigma.x)$ , then all intervals in $S^{\prime}$ projected to the $x$ axis must include $\nu^{\prime}.x$ . We have $\nu^{\prime}.x\in\bigcap_{\sigma\in S^{\prime}\cup\Gamma}\sigma.x$ , which fulfills the last condition. $\hfill\blacktriangleleft$

Lemma 35.

Let $S\subseteq N(\nu)$ , and $S^{\prime}\subseteq S$ be the stingy subset, such that

$\blacksquare$

$|S|\geq 3(k-1)$
$\blacksquare$

$|S-S^{\prime}|\leq k-1$
$\blacksquare$

$N(\nu)\subseteq\operatorname{DIR}_{up}(S)\cup\operatorname{DIR}_{down}(S)\cup S$ ( $S$ contains consecutive neighbors of $\nu$ )

Then there exists a set $S^{*}\in\operatorname{DIR}_{left}(\nu)$ , such that

$\blacksquare$

$|S^{*}|\geq k-1$
$\blacksquare$

$S^{*}.y\subseteq S.y$
$\blacksquare$

$\bigcap_{\sigma\in S^{\prime}\cup S^{*}}\sigma.x\neq\emptyset$

Proof.

The proof is symmetric to Lemma 34. $\hfill\blacktriangleleft$

$\blacktriangleright$ Lemma 23. Let $S\subset N(\nu)$ , such that

$\blacksquare$

$|S|\geq 3(k-1)$
$\blacksquare$

$|N(\nu)\cap\operatorname{DIR}_{up}(S)|\geq 3(k-1)$ ( $S$ is not among the highest elements of $N(\nu)$ )
$\blacksquare$

$|N(\nu)\cap\operatorname{DIR}_{down}(S)|\geq 3(k-1)$ ( $S$ is not among the lowest elements of $N(\nu)$ )
$\blacksquare$

$N(\nu)\subseteq\operatorname{DIR}_{up}(S)\cup\operatorname{DIR}_{down}(S)\cup S$ ( $S$ contains consecutive neighbors of $\nu$ )

At least $\frac{9}{2}(k-1)$ credits are paid to $\nu$ from horizontal segments $\sigma\in\mathbf{X}$ , such that $\sigma.y\in S.y$ .

Proof.

If $S$ contains at least $(k-1)$ generous nodes, which each contribute at least $\frac{9}{2}$ credits (Algorithm 1), the lemma holds. Otherwise, let $S^{\prime}$ be the set of stingy nodes in $S$ . We have that $|S-S^{\prime}|\leq k-2$ .

Let $R\in\operatorname{DIR}_{right}(\nu)$ be the set of nodes such that $R.y\subseteq S.y$ and for each $\sigma^{\prime}\in R$ , $\sigma^{\prime}.x$ intersects $\bigcap_{\sigma\in S^{\prime}}\sigma.x$ . According to Lemma 34, $|R|\geq k-1$ . Let $\hat{R}$ be the $k-1$ segments $\sigma\in R$ with the smallest $\min(\sigma.x)$ .

We will see that Algorithm 2 pays $\frac{9}{4}$ credits to $\nu$ from every segment $\sigma\in\hat{R}$ . Let $\sigma\in\hat{R}$ be an arbitrary segment. Let $\operatorname{DIR}_{down}(\sigma)\cap S^{\prime}=S^{\prime}_{down}$ and $\operatorname{DIR}_{up}(\sigma)\cap S^{\prime}=S^{\prime}_{up}$ . Since $|S^{\prime}|\geq 3(k-1)-(k-2)=2k-1$ , then either $|S^{\prime}_{down}|\geq k$ or $|S^{\prime}_{up}|\geq k$ . We consider the case that $|S^{\prime}_{down}|\geq k$ . The case that $|S^{\prime}_{up}|\geq k$ is symmetric. Let $Q\subseteq\operatorname{DIR}_{left}(\sigma)$ be the $(k-1)$ rightmost down-heavy vertical segments in Algorithm 2, that are each paid $\frac{9}{4}$ credits from $\sigma$ . Note that if $\nu\in Q$ , then we have shown that Algorithm 2 pays $\frac{9}{4}$ credits to $\nu$ from $\sigma$ . Since, according to our choice of $S$ , it is not among the lowest neighbors of $N(\nu)$ , then $\nu$ is down-heavy concerning $\sigma$ . This implies that $\nu\in Q$ , unless all nodes of $Q$ are to the right of $\nu$ . Since we have reached our goal in the case of $\nu\in Q$ , let us now consider only the case that $Q\in\operatorname{DIR}_{right}(\nu)$ (Figure 11). Let $\nu^{\prime}\in Q$ be the vertical segment with the largest $\min(\nu^{\prime}.y)$ .

Since $\nu$ and some point in $\sigma.x$ must intersect $\bigcap_{\sigma^{\prime}\in S^{\prime}_{down}}\sigma^{\prime}.x$ on the $x$ axis, then all segments in $Q$ (which are between them) also intersect all segments in $S^{\prime}$ when projected to the $x$ -axis. Since $\nu^{\prime}\in Q$ has the largest $\min(\nu^{\prime}.y)$ , then $S^{\prime}_{down}\cap N(v^{\prime})$ and $Q\cup\{\nu\}$ induce a biclique (Figure 11). Since $|Q\cup\{\nu\}|=k$ and there cannot exist a $K_{k,k}$ , then $|S^{\prime}_{down}\cap N(v^{\prime})|\leq k-1$ , which implies that $\min(\nu^{\prime}.y)$ is greater than $\min(S.y)$ ( $\nu^{\prime}$ does not extend far enough down to include $k$ stingy nodes below $\sigma$ ).

Since $\nu^{\prime}$ is down-heavy w.r.t $\sigma$ , then $|N(\nu^{\prime})\cap\operatorname{DIR}_{down}(\sigma)|\geq 3(k-1)$ (Definition 21). Let $\Gamma=N(\nu^{\prime})\cap\operatorname{DIR}_{down}(\sigma)$ . Note that $\Gamma.y\subseteq S.y$ , because $\min(\nu^{\prime}.y)$ is greater than $\min(S.y)$ and $\max(\Gamma.y)<\sigma.y$ . Due to how $S$ was chosen (the last condition), this implies that the nodes in $\Gamma$ that intersect $\nu$ are in $S$ . Since $k$ nodes of $S^{\prime}_{down}=\operatorname{DIR}_{down}(\sigma)\cap S^{\prime}$ cannot be in $N(\nu^{\prime})$ , then $|\Gamma\cap S^{\prime}|\leq k-1$ . Since $|S-S^{\prime}|\leq k-2$ , then $|\Gamma-S|\geq 3(k-1)-(k-1)-(k-2)=k$ .

Since all nodes that intersect $\nu$ in $\Gamma$ , must be in $S$ , then $\Gamma-S=\Gamma\cap\operatorname{DIR}_{right}(\nu)\cup\Gamma\cap\operatorname{% DIR}_{left}(\nu)$ . Since, according to our assumption, $\nu^{\prime}\in Q\subseteq\operatorname{DIR}_{right}(\nu)$ , then no horizontal segment in $\Gamma\in N(\nu^{\prime})$ can be to the left of $\nu$ without intersecting $\nu$ . Let $\hat{\Gamma}=(\Gamma-S)\cap\operatorname{DIR}_{right}(\nu)$ . Then we have $|\hat{\Gamma}|\geq k$ .

As discussed, when projected to the $x$ -axis, all segments in $Q$ intersect all segments in $S^{\prime}$ . We have $\nu^{\prime}\in Q$ and $\Gamma\in N(\nu^{\prime})$ . Therefore, on the $x$ -axis, we have a point $\nu^{\prime}.x$ that intersects $S^{\prime}$ as well as $\Gamma$ . According to how we defined $R$ , we have $\hat{\Gamma}\subseteq R$ .

Since for all $\sigma^{*}\in\Gamma$ , $\min(\sigma^{*}.x)\leq v^{\prime}.x<\min(\sigma.x)$ , then $\hat{R}$ contains $\hat{\Gamma}$ , if it contains $\sigma$ . This implies that $|\hat{R}|\geq k$ , which is a contradiction, since we chose $\hat{R}$ such that it would only contain $k-1$ segments. This implies that the case that $v\not\in Q$ is impossible.

Let $L\in\operatorname{DIR}_{left}(\nu)$ be the set of nodes such that $L.y\subseteq S.y$ and for each $\sigma^{\prime}\in L$ , $\sigma^{\prime}.x$ intersects $\bigcap_{\sigma\in S^{\prime}}\sigma.x$ . According to Lemma 35, $|L|\geq k-1$ . Let $\hat{L}$ be the $k-1$ segments $\sigma\in L$ with the largest $\max(\sigma.x)$ . The proof that Algorithm 2 pays $\frac{9}{4}$ credits to $\nu$ from every segment $\sigma\in\hat{L}$ is symmetric. $\hfill\blacktriangleleft$

Appendix E Lower bounds

Lemma 36.

If there exists a $K_{2,2}$ -free $\operatorname{\sf{PRIG}}$ graph $G$ on $n$ nodes and $m$ edges, then there exists a $K_{k,k}$ -free $\operatorname{\sf{PRIG}}$ graph $G^{\prime}$ on $(k-1)\cdot n$ nodes and $(k-1)^{2}\cdot m$ edges.

Proof.

Let $G=(U\cup V,E)$ be any $K_{2,2}$ -free graph in $\operatorname{\sf{PRIG}}$ , and $(\mathbf{X},\mathbf{Y},\phi)$ the representation of $G$ in $\operatorname{\sf{PRIG}}$ , such that $\phi:U\mapsto\mathbf{X},V\mapsto\mathbf{Y}$ , $\mathbf{X}$ is a set of points and $\mathbf{Y}$ a set of rectangles in $\mathbb{R}^{2}$ .

We construct a new graph $G=(U^{\prime}\cup V^{\prime},E^{\prime})$ , that is represented in $\operatorname{\sf{PRIG}}$ by $(\mathbf{X}^{\prime},\mathbf{Y}^{\prime},\phi^{\prime})$ , $\phi:U^{\prime}\mapsto\mathbf{X}^{\prime},V^{\prime}\mapsto\mathbf{Y}^{\prime}$ as follows. For every $\sigma\in\mathbf{X}$ , we create $k-1$ copies in $\mathbf{X}^{\prime}$ , and for every $\nu\in\mathbf{Y}$ , we create $k-1$ copies in $\mathbf{Y}^{\prime}$ . It is easy to see that $|U^{\prime}|=(k-1)|U|$ , $|V^{\prime}|=(k-1)|V|$ . Let us see the number of edges. For every $u\in U$ , $\phi(u)$ intersects with $|N(u)|$ rectangles in $G$ . In $G^{\prime}$ , a copy of $\phi(u)$ intersects with all the copies of $\phi(N(u))$ , which number in $(k-1)\cdot|N(u)|$ . Let $u^{\prime}$ be a node in $G^{\prime}$ that is represented by a copy of $\phi(u)$ . The degree of $u^{\prime}$ is $k-1$ times larger than the degree of $u$ . Since the number of nodes in $U^{\prime}$ is also $k-1$ times larger than in $U$ , then $|E^{\prime}|=|E|\cdot(k-1)^{2}$ .

Finally, let us see that $G^{\prime}$ is $K_{k,k}$ -free. Suppose by contradiction that $G^{\prime}$ has $K_{k,k}$ as a subgraph. Let $S_{U}\subseteq U^{\prime}$ and $S_{V}\subseteq V^{\prime}$ be the nodes that induce $K_{k,k}$ in $G^{\prime}$ . Then there must be at least two nodes $u,u^{*}\in U$ , whose copies form $S_{U}$ , and at least two nodes $v,v^{*}\in V$ whose copies form $S_{V}$ . Since $G^{\prime}[S_{U}\cup S_{V}]$ is a biclique, then it has edges between all pairs of nodes. There can be an edge between a pair of nodes $\{u^{\prime},v^{\prime}\}$ , $u^{\prime}\in U^{\prime}$ , $v^{\prime}\in V^{\prime}$ , if and only if that edge existed in $G$ between the nodes whose copies $u^{\prime}$ and $v^{\prime}$ are. This implies that $u,u^{*}\in U$ and $v,v^{*}\in V$ must have induced a $K_{2,2}$ in $G$ . This is a contradiction. $\hfill\blacktriangleleft$

Similarly, we can construct copies of other geometric intersection graphs.

Corollary 37.

If there exists a $K_{2,2}$ -free $\operatorname{\sf{GIG}}$ graph $G$ on $n$ nodes and $m$ edges, then there exists a $K_{k,k}$ -free $\operatorname{\sf{GIG}}$ graph $G^{\prime}$ on $(k-1)\cdot n$ nodes and $(k-1)^{2}\cdot m$ edges.

Lemma 38.

$Z_{\operatorname{\sf{CHAIN}}}(m,n;k)\geq(m+n)(k-1)-O(k^{2})$ .

Proof.

Consider a chain graph $G=(U\cup V,E)$ where $V$ corresponds to the rightward rays $\{r_{1},r_{2},\ldots,r_{n}\}$ and $U$ to the points $\{p_{1},p_{2},\ldots,p_{m}\}$ . Let all the points be placed on the real line such that each point $p_{i}$ is at coordinate $i$ . The rays $r_{1},\ldots,r_{k-1}$ start at the coordinate $0$ , which contains all the points. The remaining rays $r_{k},\ldots,r_{n}$ start at coordinate $(m-k+1.5)$ , so they contain $k-1$ points (see Figure 12). Clearly, the graph does not contain a biclique $K_{k,k}$ . The number of edges is $n(k-1)+(m-k+1)(k-1)=(n+m)(k-1)-(k-1)^{2}$ . $\hfill\blacktriangleleft$

E.1 Unit Grid Intersection Graphs

Although we do not know the correct bound for the grid intersection graphs, this section presents a lower bound construction that suggests that the leading constant of $Z(n;k)$ is likely at least $3$ . This contrasts grid intersection graphs with chordal bigraphs (where the tight bound has a leading constant $2$ ).

Our lower bound holds for the special case where all segments have unit length; such an intersection bigraph is called a Unit Grid Intersection Graph ( $\operatorname{\sf{UGIG}}$ ).

Theorem 39.

We have $Z(n;k)\geq(k-1)3n-O(k\sqrt{kn})$ for unit grid intersection graphs.

First, we construct the graph $G^{\prime}$ for $Z(n;2)\geq 3n-2\sqrt{n}$ , and then we apply Corollary 37 to get a graph for $Z(n;k)$ . Note that since the method used in the Lemma is duplication, then the new graph created in the proof will also produce a $\operatorname{\sf{UGIG}}$ . For any $t\in\mathbb{N}$ we can construct a $\operatorname{\sf{UGIG}}$ graph as follows (Figure 13).

Algorithm 3 GIG graph construction.

Note that $|\mathbf{X}|=t\cdot 2t+t\cdot 2t=4t^{2}$ and $|\mathbf{Y}|=t^{2}+t^{2}+t^{2}+t^{2}=4t^{2}$ . To count the number of edges, we count the edges incident to horizontal segments $\displaystyle\sum_{\sigma\in\mathbf{X}}\deg_{G^{\prime}}(\sigma)$ . Consider the segments that are added by the first line in the algorithm. For these segments, the degree for $j=0$ (y-coordinate $1$ ) is $2$ , and for all others, the degree is $3$ (Figure 13). The number of edges incident to the first type of horizontal segments is $3\cdot 2t^{2}-t$ . Now, consider the segments added by the second line in the algorithm. For these segments, all cases where $i=0$ have one degree less than $3$ , as well as the cases where $j=2t-1$ (the case where both are true has degree $3-2=1$ , see Figure 13). In total, the number of edges incident to these segments is therefore $3\cdot 2t^{2}-2t-t$ . The constructed graph has $|\mathbf{X}|=|\mathbf{Y}|=4t^{2}$ and the number of edges is $\displaystyle\sum_{\sigma\in\mathbf{X}}\deg_{G^{\prime}}(\sigma)=12t^{2}-4t$ .

Let faces be the areas bordered by segments. To see that the graph is $K_{2,2}$ -free, note that a $\operatorname{\sf{GIG}}$ representation of a $K_{2,2}$ would form a rectangle. Since segments in each partition have identical lengths, a rectangle that contains only non-rectangle faces cannot exist. Since none of the faces in the graph are rectangles (Figure 15), the graph is $K_{2,2}$ -free. This finishes the proof for $Z(n;2)\geq 3n-2\sqrt{n}$ .

Next, we use Corollary 37, to create a $K_{k,k}$ -free graph $G=(U\cup V,E)$ , where $|U|=|V|=4(k-1)t^{2}$ and $|E|=(k-1)^{2}(12t^{2}-4t)$ . Using the value $n=4(k-1)t^{2}$ , we get $|E|>(k-1)(3n-2\sqrt{(k-1)n})$ .

[bib.bib1] [1] Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Teresa M. Przytycka, and Sue Whitesides. Grid intersection graphs and boxicity. Discret. Math., 114(1-3):41–49, 1993. doi:10.1016/0012-365X(93)90354-V.

[bib.bib2] [2] Tom Bohman and Peter Keevash. The early evolution of the H-free process. Inventiones Mathematicae, 181(2):291–336, May 2010. doi:10.1007/s00222-010-0247-x.

[bib.bib3] [3] Romain Bourneuf, Matija Bucić, Linda Cook, and James Davies. On polynomial degree-boundedness. Advances in Combinatorics, 2024. doi:10.19086/aic.2024.5.

[bib.bib4] [4] Timothy M. Chan and Sariel Har-Peled. On the number of incidences when avoiding an induced biclique in geometric settings. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 1398–1413. SIAM, 2023. doi:10.1137/1.9781611977554.CH50.

[bib.bib5] [5] Timothy M. Chan, Chaya Keller, and Shakhar Smorodinsky. On Zarankiewicz’s problem for intersection hypergraphs of geometric objects. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazawa, Japan, volume 332 of LIPIcs, pages 33:1–33:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPICS.SOCG.2025.33.

[bib.bib6] [6] L. Sunil Chandran, Mathew C. Francis, and Rogers Mathew. Chordal bipartite graphs with high boxicity. Graphs Comb., 27(3):353–362, 2011. doi:10.1007/S00373-011-1017-2.

[bib.bib7] [7] Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, and Ryuhei Uehara. Intersection dimension of bipartite graphs. In T. V. Gopal, Manindra Agrawal, Angsheng Li, and S. Barry Cooper, editors, Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings, volume 8402 of Lecture Notes in Computer Science, pages 323–340. Springer, 2014. doi:10.1007/978-3-319-06089-7_23.

[bib.bib8] [8] Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, and Ryuhei Uehara. Ferrers dimension of grid intersection graphs. Discret. Appl. Math., 216:130–135, 2017. doi:10.1016/J.DAM.2015.05.035.

[bib.bib9] [9] Bernard Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. J. ACM, 37(2):200–212, 1990. doi:10.1145/77600.77614.

[bib.bib10] [10] Thao Do. Representation complexities of semialgebraic graphs. SIAM J. Discret. Math., 33(4):1864–1877, 2019. doi:10.1137/18M1221606.

[bib.bib11] [11] Martin Farber. Characterizations of strongly chordal graphs. Discret. Math., 43(2-3):173–189, 1983. doi:10.1016/0012-365X(83)90154-1.

[bib.bib12] [12] Jacob Fox and János Pach. Separator theorems and Turán-type results for planar intersection graphs. Advances in Mathematics, 219(3):1070–1080, 2008. doi:10.1016/j.aim.2008.06.002.

[bib.bib13] [13] Jacob Fox and János Pach. A separator theorem for string graphs and its applications. Comb. Probab. Comput., 19(3):371–390, 2010. doi:10.1017/S0963548309990459.

[bib.bib14] [14] Jacob Fox, János Pach, Adam Sheffer, Andrew Suk, and Joshua Zahl. A semi-algebraic version of Zarankiewicz’s problem. Journal of the European Mathematical Society (EMS Publishing), 19(6):1785–1810, 2017. doi:10.4171/JEMS/705.

[bib.bib15] [15] Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, and Yngve Villanger. Enumerating minimal dominating sets in chordal bipartite graphs. Discret. Appl. Math., 199:30–36, 2016. doi:10.1016/J.DAM.2014.12.010.

[bib.bib16] [16] Irith Ben-Arroyo Hartman, Ilan Newman, and Ran Ziv. On grid intersection graphs. Discret. Math., 87(1):41–52, 1991. doi:10.1016/0012-365X(91)90069-E.

[bib.bib17] [17] Oliver Janzer and Cosmin Pohoata. On the Zarankiewicz problem for graphs with bounded VC-dimension. Comb., 44(4):839–848, 2024. doi:10.1007/S00493-024-00095-2.

[bib.bib18] [18] Chaya Keller and Shakhar Smorodinsky. Zarankiewicz’s problem via $\epsilon$ -t-nets. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece, volume 293 of LIPIcs, pages 66:1–66:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SOCG.2024.66.

[bib.bib19] [19] Bettina Klinz, Rüdiger Rudolf, and Gerhard J. Woeginger. Permuting matrices to avoid forbidden submatrices. Discret. Appl. Math., 60(1-3):223–248, 1995. doi:10.1016/0166-218X(94)00054-H.

[bib.bib20] [20] Tamás Kővári, Vera T. Sós, and Pál Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicum, 3:50–57, 1954. URL: http://eudml.org/doc/210011.

[bib.bib21] [21] Jan Kratochvíl. A special planar satisfiability problem and a consequence of its NP-completeness. Discret. Appl. Math., 52(3):233–252, 1994. doi:10.1016/0166-218X(94)90143-0.

[bib.bib22] [22] Jan Kratochvíl and Jiří Matoušek. NP-hardness results for intersection graphs. Commentationes Mathematicae Universitatis Carolinae, 30(4):761–773, 1989. URL: http://eudml.org/doc/17790.

[bib.bib23] [23] Anna Lubiw. Doubly lexical orderings of matrices. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 396–404. ACM, 1985. doi:10.1145/22145.22189.

[bib.bib24] [24] Haiko Müller. Hamiltonian circuits in chordal bipartite graphs. Discret. Math., 156(1-3):291–298, 1996. doi:10.1016/0012-365X(95)00057-4.

[bib.bib25] [25] Nabil H. Mustafa and János Pach. On the Zarankiewicz problem for intersection hypergraphs. In Emilio Di Giacomo and Anna Lubiw, editors, Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, volume 9411 of Lecture Notes in Computer Science, pages 207–216. Springer, 2015. doi:10.1007/978-3-319-27261-0_18.

[bib.bib26] [26] Irina Mustata. On subclasses of grid intersection graphs. PhD thesis, Technische Universität Berlin, 2014. doi:10.14279/depositonce-4202.

[bib.bib27] [27] Pranab K. Saha, Asim Basu, Malay K. Sen, and Douglas B. West. Permutation bigraphs and interval containments. Discret. Appl. Math., 175:71–78, 2014. doi:10.1016/J.DAM.2014.05.020.

[bib.bib28] [28] Shakhar Smorodinsky. A survey of Zarankiewicz problem in geometry. CoRR, abs/2410.03702, 2024. doi:10.48550/arXiv.2410.03702.

[bib.bib29] [29] István Tomon and Dmitriy Zakharov. Turán-type results for intersection graphs of boxes. Combinatorics, Probability and Computing, 30(6):982–987, 2021. doi:10.1017/S0963548321000171.

[bib.bib30] [30] Ryuhei Uehara, Seinosuke Toda, and Takayuki Nagoya. Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs. Discret. Appl. Math., 145(3):479–482, 2005. doi:10.1016/J.DAM.2004.06.008.