The biclique of order \(k\) is the complete bipartite graph \(K_{k,k}\): the bipartite graph with sides \(a_1, \ldots, a_k\) and \(b_1, \ldots, b_k\), where \(a_i\) and \(b_j\) are adjacent for all \(i, j \in [k]\).

Let \(G\) be a graph and \(k \in \mathbb{N}\). We say that \(G\) contains the biclique of order \(k\) as a subgraph if there exist pairwise distinct vertices \(a_1, \ldots, a_k, b_1, \ldots, b_k \in V(G)\) such that \(a_i b_j \in E(G)\) for all \(i, j \in [k]\). No conditions are imposed on the remaining adjacencies between these vertices.

For \(n \in \mathbb{N}\), the comparability grid of order \(n\) is the graph with vertex set \(\{a_{i, j} : i, j \in [n]\}\) in which two distinct vertices \(a_{i, j}\) and \(a_{i', j'}\) are adjacent if and only if at least one of the following holds:

• \(i = i'\) (“same row”), or
• \(j = j'\) (“same column”), or
• \(i < i' \Leftrightarrow j < j'\) (“comparable”: \((i, j)\) and \((i', j')\) are ordered the same way in both coordinates).

No other edges are present.

Let \(G\) be a graph, \(\mathcal{K}\) a partition of \(V(G)\), and \(F \subseteq \mathcal{K}^2\) a symmetric relation. For a vertex \(v \in V(G)\), let \(\mathcal{K}(v) \in \mathcal{K}\) denote the unique part containing \(v\).

The flip of \(G\) by \((\mathcal{K}, F)\), denoted \(G \oplus F\) (leaving \(\mathcal{K}\) implicit when clear from context), is the graph with vertex set \(V(G)\) and with edges defined, for every pair of distinct vertices \(u, v \in V(G)\), by \[uv \in E(G \oplus F) \;\Longleftrightarrow\; \begin{cases} uv \notin E(G) & \text{if } (\mathcal{K}(u), \mathcal{K}(v)) \in F, \\ uv \in E(G) & \text{otherwise.} \end{cases}\]

We call \(G \oplus F\) a \(\mathcal{K}\)-flip of \(G\).

For \(k \in \mathbb{N}\), a graph \(H\) is a \(k\)-flip of \(G\) if there exists a partition \(\mathcal{K}\) of \(V(G)\) with \(|\mathcal{K}| \leq k\) and a symmetric relation \(F \subseteq \mathcal{K}^2\) such that \(H = G \oplus F\).

In particular, taking \(F = \emptyset\) yields \(G \oplus \emptyset = G\), so every graph \(G\) is a \(1\)-flip of itself (via the trivial one-part partition).

Let \(H\) be a (simple) graph and \(r \in \mathbb{N}\). The \(r\)-subdivision of \(H\), denoted \(H^{(r)}\), is the graph obtained from \(H\) by replacing every edge \(uv \in E(H)\) with a path \(u, x^{uv}_1, x^{uv}_2, \ldots, x^{uv}_r, v\), where the internal vertices \(x^{uv}_1, \ldots, x^{uv}_r\) are fresh and pairwise disjoint across edges. Equivalently, \(H^{(r)}\) has vertex set \(V(H) \,\cup\, \{x^e_i : e \in E(H), i \in [r]\}\) and edges forming the \(r+1\)-edge path along each original edge of \(H\). For \(r = 0\) we have \(H^{(0)} = H\).

The \(r\)-subdivided clique of order \(n\) is \((K_n)^{(r)}\). The \(r\)-subdivided biclique of order \(n\) is \((K_{n,n})^{(r)}\), where \(K_{n,n}\) denotes the biclique of order \(n\) (Definition Biclique). The vertices of \(V(H) \subseteq V(H^{(r)})\) are called the principal vertices of the subdivision; the fresh \(x^e_i\) are the subdivision vertices.

Let \(G\) be a graph. We say \(G\) contains \(H^{(r)}\) as a subgraph if there is an injection \(\iota\) from \(V(H^{(r)})\) to \(V(G)\) such that every edge of \(H^{(r)}\) maps to an edge of \(G\). We say \(G\) contains \(H^{(r)}\) as an induced subgraph if \(\iota\) can be chosen so that \(uv \in E(H^{(r)})\) if and only if \(\iota(u)\iota(v) \in E(G)\), for every pair of distinct \(u, v \in V(H^{(r)})\).

For \(r \geq 1\) and \(n \in \mathbb{N}\), the star \(r\)-crossing of order \(n\) is the \(r\)-subdivided biclique of order \(n\), i.e. the graph \((K_{n,n})^{(r)}\) (Definition Subdivision, Definition Biclique).

Concretely, its vertex set consists of

• the \(2n\) roots \(a_1, \ldots, a_n, b_1, \ldots, b_n\), and
• for every pair \((i, j) \in [n]^2\), \(r\) fresh path vertices \(\pi_{i,j,1}, \ldots, \pi_{i,j,r}\), pairwise disjoint across \((i, j)\).

For every \((i, j) \in [n]^2\) the edges \(a_i\,\pi_{i,j,1},\ \pi_{i,j,1}\,\pi_{i,j,2},\ \ldots,\ \pi_{i,j,r-1}\,\pi_{i,j,r},\ \pi_{i,j,r}\,b_j\) form an \((r+1)\)-edge path from \(a_i\) to \(b_j\); no other edges are present. In particular roots appear on no path, and two roots \(a_i, a_{i'}\) (resp. \(b_j, b_{j'}\)) are never adjacent.

Layer partition. The vertices of the star \(r\)-crossing of order \(n\) are partitioned into \(r + 2\) layers \(L_0, L_1, \ldots, L_{r+1}\):

• \(L_0 := \{a_1, \ldots, a_n\}\),
• \(L_\ell := \{\pi_{i,j,\ell} : i, j \in [n]\}\) for \(\ell \in [r]\),
• \(L_{r+1} := \{b_1, \ldots, b_n\}\).

Write \(\mathcal{L}_{r,n}^{\mathrm{star}} := \{L_0, \ldots, L_{r+1}\}\) for the layer partition.

Flipped star \(r\)-crossing. For \(r \geq 1\) and \(n \in \mathbb{N}\), a graph \(H\) is a flipped star \(r\)-crossing of order \(n\) if there exists a symmetric relation \(F \subseteq (\mathcal{L}_{r,n}^{\mathrm{star}})^2\) such that \(H\) is (isomorphic to) the flip \(\mathrm{Star}_{r,n} \oplus F\) of the star \(r\)-crossing \(\mathrm{Star}_{r,n}\) of order \(n\) via the layer partition \(\mathcal{L}_{r,n}^{\mathrm{star}}\) (Definition Flip).

The number of flipped star \(r\)-crossings of order \(n\) (up to isomorphism) is at most \(2^{(r+2)^2}\). Taking \(F = \emptyset\) gives the (unflipped) star \(r\)-crossing of order \(n\) as a special case.

For \(r \geq 1\) and \(n \in \mathbb{N}\), the clique \(r\)-crossing of order \(n\) is the graph obtained from the star \(r\)-crossing of order \(n\) (Definition StarCrossing) by adding, for every root \(a_i\) (\(i \in [n]\)), all edges turning \(\{\operatorname{start}(\pi_{i,j}) : j \in [n]\} = \{\pi_{i,j,1} : j \in [n]\}\) into a clique, and similarly, for every root \(b_j\) (\(j \in [n]\)), all edges turning \(\{\operatorname{end}(\pi_{i,j}) : i \in [n]\} = \{\pi_{i,j,r} : i \in [n]\}\) into a clique.

Equivalently, the vertex set is the same as for the star \(r\)-crossing and the edges are:

• the \((r+1)\)-edge path \(a_i, \pi_{i,j,1}, \ldots, \pi_{i,j,r}, b_j\) for every \((i, j) \in [n]^2\) (shared with the star \(r\)-crossing);
• for every \(i \in [n]\) and distinct \(j, j' \in [n]\), the edge \(\pi_{i,j,1} \pi_{i,j',1}\);
• for every \(j \in [n]\) and distinct \(i, i' \in [n]\), the edge \(\pi_{i,j,r} \pi_{i',j,r}\).

No other edges are present. In particular, the \((r+1)\)-edge paths are still internally vertex-disjoint across \((i, j)\), and the interior path vertices \(\pi_{i,j,\ell}\) for \(\ell \in [2, r-1]\) have the same neighborhoods as in the star \(r\)-crossing.

Layer partition. The layer partition of the clique \(r\)-crossing of order \(n\) is the same as that of the star \(r\)-crossing (Definition StarCrossing): \(\mathcal{L}_{r,n}^{\mathrm{clique}} := \{L_0, L_1, \ldots, L_{r+1}\}\) with \(L_0 = \{a_i\}\), \(L_\ell = \{\pi_{i,j,\ell} : i, j \in [n]\}\) for \(\ell \in [r]\), \(L_{r+1} = \{b_j\}\).

Flipped clique \(r\)-crossing. For \(r \geq 1\) and \(n \in \mathbb{N}\), a graph \(H\) is a flipped clique \(r\)-crossing of order \(n\) if there exists a symmetric relation \(F \subseteq (\mathcal{L}_{r,n}^{\mathrm{clique}})^2\) such that \(H\) is (isomorphic to) the flip \(\mathrm{Clique}_{r,n} \oplus F\) of the clique \(r\)-crossing \(\mathrm{Clique}_{r,n}\) of order \(n\) via the layer partition \(\mathcal{L}_{r,n}^{\mathrm{clique}}\) (Definition Flip).

The number of flipped clique \(r\)-crossings of order \(n\) (up to isomorphism) is at most \(2^{(r+2)^2}\). Taking \(F = \emptyset\) gives the unflipped clique \(r\)-crossing of order \(n\).

For \(r \geq 1\) and \(n \in \mathbb{N}\), the half-graph \(r\)-crossing of order \(n\) has the same vertex set as the star \(r\)-crossing of order \(n\) (Definition StarCrossing): the \(2n\) roots \(a_1, \ldots, a_n, b_1, \ldots, b_n\) and the interior path vertices \(\pi_{i,j,\ell}\) for \((i, j) \in [n]^2\) and \(\ell \in [r]\).

The edges are:

• for every \((i, j) \in [n]^2\), the \(r\) internal-path edges \(\pi_{i,j,1}\,\pi_{i,j,2},\ \ldots,\ \pi_{i,j,r-1}\,\pi_{i,j,r}\);
• for every \(i \in [n]\) and every \((i', j) \in [n]^2\) with \(i \leq i'\), the edge \(a_i\,\pi_{i',j,1}\);
• for every \(j \in [n]\) and every \((i, j') \in [n]^2\) with \(j \leq j'\), the edge \(b_j\,\pi_{i,j',r}\).

No other edges are present. In particular, for \(r \geq 2\), the interior path vertices \(\pi_{i,j,\ell}\) with \(\ell \in [2, r-1]\) still have only their two path-neighbors \(\pi_{i,j,\ell-1}\) and \(\pi_{i,j,\ell+1}\); the half-graph pattern differs from the star \(r\)-crossing only at the ends of the paths (near \(a_i\) and \(b_j\)).

Layer partition. The layer partition is the same as for the star \(r\)-crossing: \(\mathcal{L}_{r,n}^{\mathrm{hg}} := \{L_0, L_1, \ldots, L_{r+1}\}\) with \(L_0 = \{a_i\}\), \(L_\ell = \{\pi_{i,j,\ell} : i, j \in [n]\}\) for \(\ell \in [r]\), \(L_{r+1} = \{b_j\}\).

Flipped half-graph \(r\)-crossing. For \(r \geq 1\) and \(n \in \mathbb{N}\), a graph \(H\) is a flipped half-graph \(r\)-crossing of order \(n\) if there exists a symmetric relation \(F \subseteq (\mathcal{L}_{r,n}^{\mathrm{hg}})^2\) such that \(H\) is (isomorphic to) the flip \(\mathrm{HG}_{r,n} \oplus F\) of the half-graph \(r\)-crossing \(\mathrm{HG}_{r,n}\) of order \(n\) via the layer partition \(\mathcal{L}_{r,n}^{\mathrm{hg}}\) (Definition Flip).

The number of flipped half-graph \(r\)-crossings of order \(n\) (up to isomorphism) is at most \(2^{(r+2)^2}\). Taking \(F = \emptyset\) gives the unflipped half-graph \(r\)-crossing of order \(n\).

A graph class \(\mathcal{C}\) is weakly sparse if there exists a bound \(k \in \mathbb{N}\) such that no graph from \(\mathcal{C}\) contains the biclique of order \(k\) (Definition Biclique) as a subgraph.

A graph class \(\mathcal{C}\) is nowhere dense if for every radius \(r \in \mathbb{N}\) there exists a bound \(N_r \in \mathbb{N}\) such that no graph from \(\mathcal{C}\) contains the \(r\)-subdivided clique of order \(N_r\) (Definition Subdivision) as a subgraph.