Does there exist a class of graphs with $O(n^2)$ maximal cliques which can be realized as the 1-skeleton of a Vietoris-Rips complex in $\mathbb R^2$?

Question

Let $\mathfrak G$ be a class of graphs with quadratically many maximal cliques in the size of the vertex set. In other words, if $G=(V,E)\in \mathfrak G$ with $|V|=n$, the graph $G$ contains $O(n^2)$ maximal cliques.

Can $G$ be realized as the $1$-skeleton of a Vietoris-Rips complex $Rips(X)_r$ for some finite $X\subset \mathbb R^2$ (with the $L_2$ metric) at some scale parameter $r \geq 0$?

Recall that the Vietoris Rips complex on a finite set $X$ in a metric space at a scale parameter $r$ is the maximal simplicial complex defined by saying that a subset $S\subset X$ of $k$ points in $X$ is a $(k+1)$-simplex whenever $\text{diam} (S)\leq r$.

The Rips complex is completely determined by its $1$-skeleton, making it a clique complex.

I know that any planar or $1$-planar graph has only $O(n)$ maximal cliques, so therefore $\mathfrak G$ must not be contained in these classes, though it could potentially be $k$-planar for $k\geq 2$.

I've calculated numerous simple examples in $\mathbb R^2$ and I can't get quadratically many maximal cliques.

It seems that the geometry of $\mathbb R^2$ restricts this, but I'm not completely sure how to prove it rigorously.

Remark (edit): In full generality this question could be stated for classes of graphs having $O(n^\ell)$ maximal cliques for $\ell\geq 2$, but it seemed like asking when $\ell=2$ would be the simplest case to show.

Answer 1

The answer is, yes! In fact, in the worst case, we can have exponentially many maximal cliques.

A "unit disk graph" (UDG) is defined on a finite set in the plane, where two vertices are connected by an edge if and only if their Euclidean distance is less than or equal to 1.

Since the Vietoris-Rips complex depends on the pairwise distances, this is equivalent to realizing the graph as a Vietoris-Rips complex at scale parameter $r=1$.

Theorem 1 of this paper shows that we can have a unit disk graph with exponentially many maximal cliques in the number of vertices:

Theorem 1. The total number of cliques in a UDG grows exponentially with n in the worst case.

Proof. We illustrate this by the following example. Assume $n=2 p$. Draw a circle of diameter $1+\epsilon$, where $0<\epsilon<<1$. Place the $2 p$ nodes uniformly on the edge of the circle and label them clockwise from 1 to $2 p$. If $\epsilon$ is small enough, we have edges from any vertex $i$ to all other vertices except the diametrically opposite vertex $(i+p)$ mod $2 p$. Thus we have constructed a complete p-partite graph with its vertex set being a pair of diametrically opposite nodes i.e. $\{i, i+p\}, i=1, \ldots p$. The selection of one vertex from each of $p$ sets will form a maximal clique. Clearly we have a total of $2^p=2^{n / 2}$ maximal cliques. $\Box$