# Structural characterizations and Obstructions to Planar-Rips complexes

Vinay Sipani  Department of Mathematics
Indian Institute of Technology
Chennai - 600036
India<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Ramesh
Kasilingam  Department of Mathematics, Indian Institute Of Technology,
Chennai-600036, India<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Given a scale parameter $r>0$, the Vietoris-Rips complex of
$X\subset\mathbb{R}^{2}$ (referred to as planar-Rips complex) under the usual
Euclidean metric is a (finite) simplicial complex whose simplices are subsets
of $X$ with diameter at most $r$. This paper focuses on characterizing the
simplicial complexes that can or cannot be realized as planar-Rips complexes.
Building on the prior work of Adamszek et al., we classify, up to simplicial
isomorphism, all $n$-dimensional pseudomanifolds and weak-pseudomanifolds that
admit a planar-Rips structure, and further characterize two-dimensional, pure,
and closed planar-Rips complexes. Additionally, the notion of obstructions to
planar-Rips complexes has been introduced, laying the groundwork for
algorithmic approaches to identifying forbidden planar-Rips structures. We
also explore the correlations between planar-Rips complexes and the class of
intersection graphs called disk graphs, establishing a natural isomorphism
between the two classes. Parallely, our findings on planar-Rips complexes have
been consolidated in terms of unit disk graphs for interested readers,
depicting the significance of the topological and algebraic approaches.
Several structural and geometric properties of planar-Rips complexes have been
derived that are of independent interest.

###### Key words and phrases:

Vietoris-Rips complex, pseudomanifold, Euclidean plane, unit disk graph,
hereditary, obstruction

###### 2024 Mathematics Subject Classification:

Primary : 05E45, 68U05; Secondary : 05C10

##  1\. Introduction

The Vietoris-Rips complex is a fundamental construct in topological data
analysis (TDA), serving as a bridge between discrete data and continuous shape
analysis. With an apt representation of certain networks or practical systems
by a point set in Euclidean space, one can capture the intrinsic topological
properties that are often obscured. TDA employs the Vietoris-Rips complex to
infer these properties, encoding the data’s shape into a combinatorial
framework. This in turn, facilitates the study of intricate geometry and
connectivity within the system or the network at various scales [23].

This paper is specifically streamlined towards the study of Vietoris-Rips
complexes of planar point sets. With the appealing interplay of geometry,
topology, and combinatorics, this study is partly motivated by the ability of
planar-Rips complexes to faithfully represent proximity-based relationships in
the Euclidean plane, making them a useful tool for modeling various phenomena.
To name a few, these complexes find their potential applications in wireless
and sensor networks [13, 14, 15, 7], social network analysis [18], swarm
robotics [17], and motion planning[16] where proximity and connectivity play
pivotal roles in modeling interactions. Formally, the planar-Rips complex can
be defined as follows:

######  Definition 1.1 (Planar-Rips complex).

Given a finite subset $X\subset\mathbb{R}^{2}$ with the usual Euclidean metric
and a scale parameter $r>0$, the Vietoris-Rips complex of planar point set $X$
(also called planar-Rips complex) is a (finite) simplicial complex whose
simplices are subsets of $X$ with diameter at most $r$. We shall denote it by
$\mathcal{R}(X;r)$ [1].

One of the fundamental problems in TDA is the characterization of the planar-
Rips complexes, at least up to homotopy. Our study is primarily driven by the
works of [19, 20, 1, 2, 3] where the respective authors have widely addressed
the characterization problem of planar-Rips complexes at various scales. In
his paper [19], Hausmann demonstrated that up to homeomorphism, every
$n$-sphere can be represented as a planar-Rips complex for some subset of
circle $\mathbb{S}^{1}$. Adamszek and Adams in [3] obtain a wide range of
homotopy types of planar-Rips complexes for various subsets of circle
$\mathbb{S}^{1}$. In [1], Chambers et al. prove that the planar-Rips complexes
have free fundamental group. As a consequence, one can verify using long exact
sequences that every finite $2$-dimensional planar-Rips complex has homotopy
type of wedge of circles and $2$-spheres. However, the problem of whether
every planar-Rips complex is homotopy equivalent to wedge of spheres still
remains open [2, Problem 7.3].

######  Definition 1.2.

A finite simplicial complex $K$ with the vertex set $V$ is said to admit a
planar-Rips structure if there exists an injective map $f:V\to\mathbb{R}^{2}$
such that $K$ is isomorphic to the planar-Rips complex $\mathcal{R}(f(V);r)$
for some $r>0$.

This paper is centered around determining the simplicial complexes that do not
admit planar-Rips structure. Therefore, with the scale-invariance under
consideration, we fix $r=1$ throughout and use the notation $\mathcal{R}(X)$
instead of $\mathcal{R}(X;1)$.

Our paper builds on the prior work by M. Adamaszek et al. of classifying all
normal pseudomanifolds admitting planar-Rips structure [2, Theorem 6.3]; They
show that the normal psedomanifolds which admit planar-Rips structure are
precisely the cross-polytopal spheres. In this paper, we extend this result to
a larger class of pure simplicial complexes. Our main results are as follows:

######  Theorem A.

The n-dimensional cross-polytopal spheres ($n\geq 2$) are the only
pseudomanifolds that admit planar-Rips structure.

(cf. Theorem 3.7 and Theorem 3.15 ).

This will be an inductive proof. We use this to further give a planar-Rips
classification of $n$-dimensional weak-pseudomanifolds, whose each strongly
connected component is a pseudomanifold.

######  Theorem B.

An n-dimensional weak-psedomanifold ($n\geq 2)$ admitting a planar-Rips
structure is isomorphic to an iterated chain of $n$-dimensional cross-
polytopal spheres. Further, they are homotopy equivalent to wedge sum of
circles and $n$-spheres.

(cf. Theorem 3.18 and Corollary 3.19 ).

The tools from [1, 2] and the proximity relations derived towards proving the
above two theorems are further applicable towards the characterization of
$2$-dimensional pure and closed simplicial complexes that admit planar-Rips
structure.

######  Theorem C.

Suppose $K$ is a $2$-dimensional pure and closed simplicial complex admitting
a planar-Rips structure, then

  * (a)

$K$ contains a copy of octahedron as an induced subcomplex.

  * (b)

The number of copies of octahedron as induced subcomplex in $K$ is same as its
second Betti number $b_{2}(K)$.

(cf. Theorem 4.7 and Proposition 4.14 ).

A significant implication of our study is towards characterization of a class
of intersection graphs called unit disk graphs (UDGs). Notably, a natural
isomorphism exists between the category of planar-Rips complexes and the
category of unit disk graphs, with unit disk graphs being precisely the
1-skeleton of planar-Rips complexes. The literature on unit disk graphs and
some of their applications can be found in [4, 5, 6]. In light of this
isomorphism, the graph analogs to Theorems A,B,C have been substantiated in
Section 5. For instance, the following theorem is a direct consequence of C,
which significantly streamlines the recognition process for a class of unit
disk graphs with all maximal cliques of size $3$.

######  Theorem D.

Let $G$ be a connected graph having clique number $\omega(G)=3$ and
$\mathrm{degree}(e)\geq 2$ for every edge $e$ in $G$. If $G$ admits a unit
disk graph structure, then

  * (a)

$G$ contains an induced subgraph isomorphic to complete tripartite graph
$K_{2,2,2}$.

  * (b)

Every edge is contained in at most two distinct copies of $K_{2,2,2}$.

  * (c)

Any edge $e$ with $\mathrm{degree}(e)\geq 3$ is contained in at least one copy
of $K_{2,2,2}$.

(cf. Corollary 5.4).

Another intriguing aspect of planar-Rips complexes is that they satisfy
hereditary property. This means that every induced subcomplex is also a
planar-Rips complex. It is well established that any hereditary class of
simplicial complexes can be fully characterized in terms of minimal forbidden
induced subcomplexes called obstructions. These obstructions represent
critical subcomplex patterns that cannot appear as induced subcomplexes within
any complex in the class. For example, the hereditary class of flag complexes
can be defined as the simplicial complexes that do not contain the boundary
complex of any $n$-simplex ($n>1$) as an induced subcomplex. In essence, any
simplicial complex that does not admit a planar-Rips structure further
contains a ‘minimal’ forbidden induced subcomplex. The significance of
defining the class of planar-Rips complexes in terms of obstructions lies in
its potential for algorithmic simplification in identifying planar-Rips
complexes. This, in turn, offers more insight into the limitations and
restrictions of associated systems or networks.

Following Theorems A,B,C, we have indeed obtained a wide spectrum of
simplicial complexes that do not admit a planar-Rips structure. This opens up
the possibility of obtaining a large collection of obstructions to planar-Rips
complexes by extracting each one as an induced subcomplex from the forbidden
planar-Rips structures. The feasibility of establishing such a framework has
been demonstrated by a few examples in Section 5. For example, Theorem 5.13
substantiates an obstruction to planar-Rips complex, derived from a
triangulation of the projective space $\mathbb{R}P^{2}$.

In essence, the proximity relations and the structural/geometric
characterizations established throughout this paper are of independent
interest, laying the groundwork for an algorithmic approach to utilizing
planar-Rips complexes.

Organization of the paper: In Section 2, a background overview of planar-Rips
complexes is presented by introducing key topological concepts and discussing
the proximity relations for points in the Euclidean plane relevant to this
paper. Section 3 delves into developing the necessary geometric aspects to
prove A and B, leading to a complete classification of planar-Rips complexes
with pseudomanifold and weak-pseudomanifold structures. Section 4 focuses on
establishing the structural characterization of two-dimensional closed planar-
Rips complexes as part of proving C. Lastly, in Section 5, we consolidate our
findings on planar-Rips complexes in terms of unit disk graphs to prove D. In
addition, the hereditary property of planar-Rips complexes has been explored
and the notion of obstructions to planar-Rips complexes has been
conceptualized. Illustrative examples are provided to demonstrate the utility
of this concept.

##  2\. Preliminaries

Throughout this paper, we consider the point set $X$ to be a finite subset of
$\mathbb{R}^{2}$ and the planar-Rips complex $\mathcal{R}(X)$ to be connected.
Further, the geometric realization of $\mathcal{R}(X)$ is considered while
referring to the associated topological properties of $\mathcal{R}(X)$. We say
two points/vertices are adjacent in $\mathcal{R}(X)$ if the distance between
them is less than $1$ i.e. there is an edge between them in $\mathcal{R}(X)$.

We shall also use the following notation: Given a simplicial complex $K$ on a
vertex set $V$, the link of a simplex $\sigma$ in $K$ is defined to be
$\left\\{\tau\in K\mid\tau\cap\sigma=\emptyset,\tau\cup\sigma\in K\right\\}$,
and is denoted by $\mathrm{Lk}(\sigma)$. For a subset $U$ of $V$, denote the
induced subcomplex of $K$ on $U$ by ${\left\langle{U}\right\rangle}$.

We now define the concept of “shadow” of a planar-Rips complex
$\mathcal{R}(X)$ inside $\mathbb{R}^{2}$. This notion was originally
introduced in a broader context for $\mathbb{R}^{n}$ by Chambers et al.[1] to
simplify the computability. Likewise, we employ the concept of shadow to
simplify the representation of proximity relations and certain topological
properties of planar-Rips complexes.

######  Definition 2.1 (Shadow, projection map).

Given a finite set $X\subset\mathbb{R}^{2}$, the shadow $\mathcal{S}(X)$ is
the image of the planar-Rips complex $\mathcal{R}(X)$ under the projection map
$p:\mathcal{R}(X)\to\mathbb{R}^{2}$ which maps each vertex in $X$ to the
corresponding point inside $\mathbb{R}^{2}$, and extends linearly to the
simplices of $\mathcal{R}(X)$. More precisely,

$\mathcal{S}(X):=\bigcup_{\begin{subarray}{c}Y\subseteq X,\ |Y|\leq n+1\\\
\mathrm{diam}(Y)<1\end{subarray}}\mathrm{conv}\ Y$

######  Example 2.2.

Figure 1 illustrates a point set $X$ in $\mathbb{R}^{2}$, forming a four-
dimensional planar-Rips complex $\mathcal{R}(X)$. Along with it is a
representation of projection map onto its shadow $\mathcal{S}(X)$.

Figure 1. An illustration of projection of planar-Rips complex
$\mathcal{R}(X)$ onto its shadow $\mathcal{S}(X)$ inside $\mathbb{R}^{2}$

The following result by Chambers et al. in [1] depicts the topological
faithfulness of the projection map $p$, representing the fundamental group of
$\mathcal{R}(X)$ in terms of its shadow $\mathcal{S}(X)$.

######  Theorem 2.3.

[1] Let $X\subset\mathbb{R}^{2}$ be a finite subset and
$p:\mathcal{R}(X)\to\mathcal{S}(X)$ be the projection map, then $p$ induces a
$\pi_{1}$-isomorphism, hence implying that the fundamental group is free.

It has been readily apparent in our study that the applicability of proximity
relations between the points is quite inevitable for the study of planar-Rips
complexes. Hence, there is a need to deduce many more such properties in
pertinence to the geometry of $\mathbb{R}^{2}$. The following are some key
properties of planar-Rips complexes that will be referenced throughout this
paper.

######  Lemma 2.4.

[1, Proposition. 2.1] Suppose $X\subset\mathbb{R}^{2}$ and let $A,B,C,D$ be
four points in $X$ such that the point $A$ is adjacent to $B$, and $C$ is
adjacent to $D$ but not $A$ in $\mathcal{R}(X)$. Further, the segments
$\overline{AB}$ and $\overline{CD}$ intersect in the shadow $\mathcal{S}(X)$.
Then $B$ is adjacent to $D$ in $\mathcal{R}(X)$.

######  Lemma 2.5.

The graph of $1$-skeleton of a planar-Rips complex $\mathcal{R}(X)$ cannot
contain an induced subgraph isomorphic to the bipartite graph $K_{1,6}$

The above result is a direct consequence of [4, Lemma 3.2], and has been
elaborately explained in Section 5.

######  Lemma 2.6.

Given $X\subset\mathbb{R}^{2}$, let $A$ be a subset of $X$ and $\sigma$ be a
simplex such that $A\subseteq Lk(\sigma)$ inside $\mathcal{R}(X)$. Suppose a
simplex $\gamma$ is in the convex hull of $A$, then $\gamma\in Lk(\sigma)$ and
every vertex of $\gamma$ is adjacent to at least one vertex of $A$ in
$\mathcal{R}(X)$.

###### Proof.

Let $u$ and $v$ be any vertex in $\sigma$ and $\gamma$ respectively. Firstly,
by Caratheodory’s theorem, there exists vertices $a_{1},a_{2}\in A$ (not
necessarily distinct) such that $v\in conv(u,a_{1},a_{2})$. Now, since
$d(u,a_{i})\leq 1$ for all $i=1,2$, we have $d(u,w)\leq 1$ for any $w\in
conv(u,a_{1},a_{2})$. Since this is true for any $u\in\sigma$, we have
$\gamma\in Lk(\sigma)$.

Now consider the unit circles inside $\mathbb{R}^{2}$ centered at points
$a_{1},a_{2}$. Since the union of these circles covers $conv(u,a_{1},a_{2})$,
the point $v$ is adjacent to at least one of $a_{1},a_{2}$. ∎

######  Remark 2.7.

The above result generally holds even for the Vietoris-Rips complex of $X$
when $X\subset\mathbb{R}^{n}$ under the usual metric, and a similar proof is
applicable.

######  Proposition 2.8.

For a Vietoris-Rips complex on planar point sets, the convex hulls of any two
connected components in the link of a vertex cannot intersect in the shadow
$\mathcal{S}(X)$.

###### Proof.

Suppose $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are any two components of link
of a vertex inside $\mathcal{R}(X)$. By Lemma 2.6, one of the convex hulls of
$V(C_{1})$ and $V(C_{2})$ cannot contain in the other. Further, from Lemma
2.4, the convex hulls cannot intersect on their boundaries. ∎

##  3\. Classification of Rips complexes with weak-pseudomanifold structure

In this section, we present a complete classification of well-behaved spaces
known as pseudomanifolds and weak-pseudomanifolds that admit planar-Rips
structure. To accomplish this, we first introduce the necessary terminologies
and tools before proceeding with the proof of A by induction. Subsequently, we
use this to further prove B.

The dimension of a simplex will be one less than its cardinality. The
dimension of a simplicial complex is defined to be equal to the supremum of
all $n$’s such that $K$ has a face of dimension $n$. A simplex in $K$ is
called maximal or a facet if it is not contained in another larger simplex. An
$n$-dimensional simplicial complex is said to be pure if every maximal simplex
is of dimension $n$.

######  Definition 3.1 (Strongly connected simplicial complex).

A pure simplicial complex is said to be strongly connected if for any two
facets $\sigma$ and $\gamma$, there exists a sequence of $n$-simplices, say
$\lambda_{1},\lambda_{2},\dots\lambda_{k},$ such that $\lambda_{1}=\sigma,\
\lambda_{k}=\gamma$ and $\lambda_{i}\cap\lambda_{i+1}$ is an $(n-1)$-simplex
for all $1\leq i\leq k-1$.

We now recursively define the classes of pure simplicial complexes viz. weak-
pseudomanifolds, pseudomanifolds, and normal pseudomanifolds

######  Definition 3.2.

  * (a)

An $n$-dimensional simplicial complex is said to be a weak pseudomanifold if
it is pure and each $(n-1)$-simplex is contained in exactly two $n$-simplices.

  * (b)

An $n$-dimensional weak-pseudomanifold is called a pseudomanifold if it is
strongly connected.

  * (c)

An $n$-dimensional pseudomanifold is said to be a normal pseudomanifold if the
link of each simplex of codimension atleast two is connected.

The following result by Adamaszek et al. in [2] gives a complete
classification of normal pseudomanifolds that admit a planar-Rips structure.

######  Theorem 3.3.

[2, Theorem 6.3] : For any $d\geq 2$ and any finite subset
$X\subset\mathbb{R}^{2}$, if the planar-Rips complex $\mathcal{R}(X)$ is a
$d$-dimensional normal pseudomanifold then $\mathcal{R}(X)$ is isomorphic to
boundary complex of the $(d+1)$ dimensional cross-polytope.

Hence, apart from crosspolytopal spheres, no other manifold admits a planar-
Rips structure inside $\mathbb{R}^{2}$. But it is interesting to determine the
class of manifolds that admit a planar-Rips structure at least upto homotopy
equivalence. For instance, the methodology in proving whether or not the
manifold $\mathbb{S}^{1}\times\mathbb{S}^{2}$ admits a planar-Rips structure
upto homotopy equivalence will itself make a pavement of myriad tools to study
the classification of planar-Rips structures inside $\mathbb{R}^{2}$.

A simplex of a finite weak-pseudomanifold of codimension at least two will be
called singular if its link is not connected. The proposition below provides
an implication of the precise number of connected components in the link of a
singular vertex when $\mathcal{R}(X)$ is a weak-pseudomanifold.

######  Proposition 3.4.

For $X\subset\mathbb{R}^{2}$, suppose the planar-Rips complex $\mathcal{R}(X)$
is an $n$-dim weak-pseudomanifold where $n\geq 2$, then the link of any
simplex of codimension at least two can have at most two strongly connected
components.

###### Proof.

On contrary, suppose there are more than two strongly connected components in
the link of some $k$-simplex, say $\sigma$, where $0\leq k\leq n-2$ . We have
that the link of the simplex $\sigma$ is again a weak-pseudomanifold of
dimension $n-k-1$. Since each strong component is a pseudomanifold and admits
a planar-Rips structure, choose two non-adjacent vertices from each of them,
hence forming an induced subgraph $K_{1,6}$ . This is not possible owing to
Lemma 2.5. ∎

######  Corollary 3.5.

For $X\subset\mathbb{R}^{2}$, if $\mathcal{R}(X)$ is an $n$-dim weak-
pseudomanifold ($n\geq 2$), then the link of any $(n-2)$ simplex can have at
most 11 vertices. Further, it is either a cycle or a disjoint union of exactly
two cycles.

The following lemma from [8] provides a general representation of all two-
dimensional weak-pseudomanifolds, specifically for two-dimensional
pseudomanifolds by restricting to the strongly connected components.

######  Lemma 3.6 (Classification of $2$–dimensional weak-pseudomanifolds).

Any compact weak-pseudomanifold of dimension $2$ consists of a collection of
compact $2$–manifolds without boundary glued or self–glued along a finite
number of points. More technically: such a weak-pseudomanifold $X$ is the
quotient space of a disjoint union of compact 2–manifolds without boundary
such that if $q$ is the quotient map, then all points $x\in X$ satisfy
$\\#\left\\{q^{-1}(x)\right\\}<\infty$ and for all but finitely many $x\in X$,
$\\#\left\\{q^{-1}(x)\right\\}=1$.

Thus, a pseudomanifold $X$ is the quotient space of a compact 2-manifold
without boundary by taking a self-identification of finite sets of points.
With the aim of classifying all planar-Rips complexes having a weak-
pseudomanifold structure, we first extend Theorem 3.3 for a pseudomanifold. We
begin by proving the two-dimensional case.

######  Theorem 3.7.

For any $X\subset\mathbb{R}^{2}$, the planar-Rips complex on $X$ having a two-
dimensional pseudomanifold structure is isomorphic to the boundary complex of
octahedron.

###### Proof.

(a) $\mathcal{R}(X)$: Pinched Torus.

(b) $\mathcal{R}(X-v)$: After deleting the singular vertex.

Figure 2. A sphere with self-identification of two points is homeomorphic to
pinched torus. The link of its singular vertex $v$ has two connected
components. Here, both $\mathcal{R}(X)$ and $\mathcal{R}(X-v)$ do not admit
planar-Rips structure.

By Theorem 2.3, the fundamental group of $\mathcal{R}(X)$ is free. Hence, by
the structure theroem for (weak) pseudomanifolds (Lemma 3.6), the
pseudomanifold $\mathcal{R}(X)$ is homeomorphic to the quotient space of
sphere $\mathbb{S}^{2}$ by taking a self-identification of finite sets of
points; let $q:\mathbb{S}^{2}\to\mathcal{R}(X)$ be the associated quotient
map.

Let $\tilde{X}$ be the set of singular vertices (vertices whose links are not
connected) in $\mathcal{R}(X)$. For any vertex $v\in X$, since $Lk(v)$ has at
most two disjoint cycles (by Proposition 3.4), the set $q^{-1}(v)$ can have at
most two points, and $q^{-1}(u)\cap q^{-1}(v)=\emptyset$ for $u\neq v$; hence,
$|q^{-1}(\tilde{X})|=2|\tilde{X}|$. Now, consider the planar-Rips complex
$\mathcal{R}(X-\tilde{X})$ which is homotopy equivalent to a sphere with $2m$
points deleted, where $|\tilde{X}|=m$. Each removed point $v_{i}$ from the
sphere corresponds to a cycle $\mathcal{C}_{i}$ in the link of the singular
vertex $q(v_{i})$ in $\mathcal{R}(X)$. Figure 2 shows an illustration for
$m=1$ case. Further, the cycle $[p(\mathcal{C}_{i})]$ is non-trivial in
$\pi_{1}(\mathcal{S}(X-\tilde{X}))$ since the projection map
$p:\mathcal{R}(X-\tilde{X})\to\mathcal{S}(X-\tilde{X})$ induces a
$\pi_{1}$-isomorphism (Theorem 2.3).

From Proposition 2.8, the convex hulls of any two of the $2m$ cycles in
$\mathcal{R}(X-\tilde{X})$ cannot intersect; hence the shadow
$\mathcal{S}(X-\tilde{X})$ is homotopy equivalent to wedge of $2m$ copies of
$\mathbb{S}^{1}$. This is possible only if $m=0$ since for $m\geq 1$, the Rips
complex $\mathcal{R}(X-\tilde{X})$ is homotopy equivalent to a wedge of
$(2m-1)$ copies of $\mathbb{S}^{1}$. Therefore, the link of every vertex is
connected and the conclusion follows by the virtue of Theorem 3.3.

∎

Now to extend the result of the above theorem to $n$-dimensional
pseudomanifold, we use induction. In order to do so, we first introduce
certain prerequisite proximity relations for points in the Euclidean plane.

######  Definition 3.8 (Antipodal point).

: Given the boundary complex of $(n+1)$-dimensional cross-polytope, say
$\mathcal{O}_{n}$, the antipodal point of any vertex $v\in\mathcal{O}_{n}$ is
the vertex in $\mathcal{O}_{n}$ not adjacent to $v$ and is denoted by
$\bar{v}$.

######  Lemma 3.9.

For $X\subset\mathbb{R}^{2}$, let $|X|=2n$ and $\mathcal{R}(X)$ be isomorphic
to the boundary complex of $n$-dimensional cross-polytope($n\geq 2$). Then any
$x\in X$ is not in the convex hull of the remaining vertices i.e. the shadow
$\mathcal{S}(X)$ is a simple convex polygon with $2n$ sides.

###### Proof.

Let if possible, there exists $x\in X$ such that $x\in conv(X-x)$. Then by
Caratheodory’s theorem, there exists vertices $a,b,c\in(X-x)$ such that
$x\in\mathrm{conv}\left\\{a,b,c\right\\}$. Now there are two cases to
consider.

  1. (1)

Suppose one of the points $a,b,c$ is an antipodal point of $x$; without loss
of generality, assume $a$ to be the antipodal point $\bar{x}$. Since
$d(\bar{x},b)<1$ and $d(\bar{x},c)<1$ in $\mathcal{R}(X)$, the distance
between $\bar{x}$ and any point in $\triangle\bar{x}bc$ is less than 1 i.e.
$d(\bar{x},x)<1$ which is absurd.

  2. (2)

Suppose none of the points $a,b,c$ is the antipodal point $\bar{x}$. Then from
Lemma 2.6, we have $x\in Lk(\tilde{x})$ i.e. $d(\bar{x},x)<1$ which is again
absurd.

∎

######  Lemma 3.10.

[2, Lemma 6.1] Let $\mathcal{S}$ be a simple polygon in $\mathbb{R}^{2}$ and
$v$ be a point outside or on $\mathcal{S}$. Suppose further that for every
vertex $P$ of $\mathcal{S}$, all the intersections of the ray
$vP^{\rightarrow}$ with $\mathcal{S}$ lie between $v$ and $P$. Then there is
an edge $AB$ of $\mathcal{S}$ such that for any vertex $P$ of $\mathcal{S}$
the segments $vP$ and $AB$ have non-empty intersection.

We refer to such a point $v$ as guard point. The motivation to use this
terminology stems from the Art Gallery problem, a prominent concept in
Computational Geometry. In the art gallery problem [9, p. 8], a guard point
(or sometimes called point guard) refers to a point on or inside a polygon
from which the entire interior of the polygon can be observed. It is a
location from where a guard can have an unobstructed line of sight to every
point inside the gallery. In our case, the guard points are considered to be
lying strictly outside the polygon, and the guard points are needed to have
every line of sight passing through an edge of the polygon. Furthermore, from
Lemma 3.10, it is sufficient for the guard point to have a clear line of sight
to only the vertices of the simple polygon.

######  Definition 3.11 (Guard point of a simple polygon along a side).

Given a simple polygon $\mathcal{S}$ having an edge $AB$, a point $v$ outside
$\mathcal{S}$ is called a guard point of $\mathcal{S}$ alongside $AB$ if for
any vertex $P$ of $\mathcal{S}$, the segments $vP$ and $AB$ intersect.

A fundamental problem in computational geometry is determining the position of
a point with respect to a line segment. This involves finding on which side of
the line does the point lie, and can be used as a building block to solve more
complex problems like line segment intersection and finding the convex hull of
a set of points. In summary, these ideas and methods in combinatorial topology
for the Euclidean plane case play a fundamental role for effectively analyzing
the geometric structures and their properties.

###  3.1. Position of a point relative to a line:

To determine on which side of a given line a point lies, we can use the cross-
product of two vectors. Given points $A=(x_{1},y_{1})$ and $B=(x_{2},y_{2})$,
let $L_{AB}$ represent the line joining them. Let $P=(x,y)$ be a point whose
position relative to $L_{AB}$ needs to be determined. Consider the two vectors
$\vec{AB}=(x_{2}-x_{1},y_{2}-y_{1})$ and $\vec{AP}=(x-x_{1},y-y_{1})$, and
take their cross-product,
$r=\vec{AB}\times\vec{AP}=(x-x_{1})(y_{2}-y_{1})-(y-y_{1})(x_{2}-x_{1})$. The
sign of $r$ indicates the point $P$’s position with respect to line $L_{AB}$:

  1. -

if $r>0$, then the point is to the left of the line $L_{AB}$; Denote it by
$P\in L^{+}_{AB}$.

  2. -

if $r<0$, then the point is to the right of the line $L_{AB}$; Denote it by
$P\in L^{-}_{AB}$.

  3. -

if $r=0$, then the point is on the line $L_{AB}$; Denote it by $P\in L_{AB}$.

The union of line $L_{AB}$ and the region $L^{+}_{AB}$ will be denoted by
$cl(L^{+}_{AB})$, which is same as taking the closure of $L^{+}_{AB}$ in usual
topological sense. Note that the order of the points $A$ and $B$ is
significant while determining the position of point $P$ relative to the line
$L_{AB}$. The orientation of the line is taken to be in the direction from $A$
to $B$. Moreover, it can be easily checked that $L^{+}_{AB}=L^{-}_{BA}$.

Additionally, by determining on which side of a line a point lies, we can
efficiently test whether a given point lies within the convex hull of three
points in the Euclidean plane. For instance, given three non-collinear points
$a,b,c$, the region $cl(L^{-}_{ab})\cap cl(L^{-}_{bc})\cap cl(L^{-}_{ca})$ or
$cl(L^{+}_{ab})\cap cl(L^{+}_{bc})\cap cl(L^{+}_{ca})$ corresponds to the
$\triangle abc$ depending on whether the points $a,b,c$ are in clockwise($c\in
L^{-}_{ab}$) or counterclockwise($c\in L^{+}_{ab})$ order respectively.

For example, the next lemma which we shall use in our subsequent results, is
an immediate consequence of the above approach and can be easily verified.

######  Lemma 3.12.

Let $A,B,C$ be three non-collinear points inside $\mathbb{R}^{2}$. Consider
the set

$\mathcal{H}=\left\\{X\in\mathbb{R}^{2}\mid
C\in\mathrm{conv}\left\\{A,B,X\right\\}\right\\}$

Then

  1. (1)

$\mathcal{H}=cl(L^{-}_{AC})\cap cl(L^{+}_{BC})$, when $A,B,C$ are in clockwise
order

  2. (2)

$\mathcal{H}=cl(L^{+}_{AC})\cap cl(L^{-}_{BC})$, when $A,B,C$ are in
counterclockwise order

Figure 3. The two cases of Lemma 3.12: The gray region(extended) denotes the
set $cl(L^{-}_{AC})\cap cl(L^{+}_{BC})$ or $cl(L^{+}_{AC})\cap
cl(L^{-}_{BC})$, depending on whether points are in clockwise or
counterclockwise order respectively.

###  3.2. Perpendicular bisector

Given any two points $a$ and $b$ in $\mathbb{R}^{2}$, the line of
perpendicular bisector of $a$ and $b$ will be denoted by $L_{a|b}$ and the set
of all points whose distance from $a$ is strictly less than distance from $b$
will be denoted by $\mathcal{P}_{a<b}$ i.e.

$\mathcal{P}_{a<b}:=\left\\{x\in\mathbb{R}^{2}\mid d(a,x)<d(b,x)\right\\}$

Note that the set $\mathcal{P}_{a<b}$ inside $\mathbb{R}^{2}$ is same as the
set of all points that lie on the same side of the line $L_{a|b}$ as the point
$a$ does i.e. $\mathcal{P}_{a<b}=L^{+}_{a|b}$. Moreover, it can be easily
checked that $L^{+}_{A|B}=L^{-}_{B|A}$.

######  Lemma 3.13.

Let $A,B,C,D$ be four points in $\mathbb{R}^{2}$ such that no three points are
collinear, the segments $\overline{AB}$ and $\overline{CD}$ intersect, and the
distance of $D$ from $C$ is less than the distance from both $A$ and $B$.
Suppose $P$ is any point whose distance from $C$ is greater than the distance
from both $A$ and $B$, then the point $D$ is in the convex hull of points
$A,B,\ \text{and}\ P$ i.e. $D\in\mathrm{conv}\left\\{A,B,P\right\\}$.

###### Proof.

Figure 4.  The blue and green regions denote the respective possible locations
for points $D$ and $P$ corresponding to a specific arrangement of points $A$,
$B$ & $C$ satisfying Lemma 3.13. The point $P$ lies in the region of points
that satisfy $D\in\mathrm{conv}\left\\{A,B,P\right\\}$.

.

Since the segments $\overline{AB}$ and $\overline{CD}$ intersect, and no three
points are collinear, the points $C$ and $D$ lie on either side of the line
$L_{AB}$; assume without loss of generality, $C\in L^{-}_{AB}$ and $D\in
L^{+}_{AB}$. Further, the point $D$ being closer to $C$ than both $A$ and $B$
implies $D\in L^{-}_{A|C}\cap L^{+}_{C|B}$. Likewise, $P\in L^{+}_{A|C}\cap
L^{-}_{C|B}$. Now it can be easily checked that $L^{+}_{A|C}\cap
L^{-}_{C|B}\subset L^{+}_{AD}\cap L^{-}_{BD}$ i.e. $P\in L^{+}_{AD}\cap
L^{-}_{BD}$ (See Figure 4 for an illustration). Consequently,
$D\in\mathrm{conv}\left\\{A,B,P\right\\}$ as follows from Lemma 3.12.

∎

######  Lemma 3.14.

Let $r>0$. Suppose $A,B,C,D,X,Y$ are six points in $\mathbb{R}^{2}$ satisfying
the following:

  1. (1)

$ABCD$ is a quadrilateral with sides of length less than $r$ and diagonals of
length at least $r$

  2. (2)

The point $X$ is a guard point of $ABCD$ along the side $AB$, and distance of
$X$ from the points $C$ and $D$ is less than $r$.

  3. (3)

The distance of $Y$ from points $A$ and $B$ is less than $r$, and distance of
$Y$ from $X$ is at least $r$.

Then the point $Y$ is a guard point of $ABCD$ along the side $CD$. Further,
the distance of $Y$ from points $C$ and $D$ is less than $r$.

###### Proof.

Figure 5. An illustrative example for Lemma 3.14: A possible arrangement of
points $A,\ B,\ C,\ D$ and $X$ satisfying the hypotheses. Corresponding to
this arrangement, the point $Y$ is located in the gray region.

.

From $(1)$, it follows that the quadrilateral $ABCD$ is simple and convex. The
points $A$, $B$, and $X$ are not collinear as follows from $(2)$ and $(3)$.
Hence, without loss of generality, assume the points $C$ and $D$ are on the
left side and $X$ on the right side of the line $L_{AB}$. The point $Y$ being
closer to both $A$ and $B$ than $X$ implies $Y\in L^{+}_{A|X}\cap L^{-}_{X|B}$
(An illustration of a possible arrangement is shown in Figure 5). We have the
following sequential observations:

  1. (a).

$C\in L^{-}_{A|X}$ since the point $C$ is closer to $X$ than $A$. Likewise,
$D\in L^{+}_{X|B}$ since the point $D$ is closer to $X$ than $B$.

  2. (b).

This implies $L^{+}_{A|X}\cap
L^{-}_{X|B}\subset\mathrm{conv}\\{A,B,C,D,X\\}\cup L^{-}_{CD}$.

  3. (c).

As a consequence, $Y\in L^{-}_{CD}$ since
$Y\notin\mathrm{conv}\\{A,B,C,D,X\\}$, given that $d(X,Y)\geq r$.

Hence the point $Y$ lies in the exterior region of side $CD$. From hypothesis
$(3)$, we have $d(Y,B)<d(D,B)$ implying that $Y$ lies on right side of the
line $L_{BD}$ i.e. $Y\in L^{-}_{BD}$. Likewise, $Y\in L^{+}_{AC}$. Further,
the points $C$ and $D$ cannot be inside $\triangle YAB$ since $d(B,D)\geq r$.
This adds further restriction on the location where the point $Y$ can lie as
apparent in Figure 5. Therefore, the point $Y$ is guard point of $ABCD$ along
the side $CD$. Consequently, it follows from Lemma 2.4 that the distance of
$Y$ from both $C$ and $D$ is less than $r$.

∎

The above lemma has a further implication that $X$ is a guard point along the
side $AB$ if and only if $Y$ is a guard point along the side $CD$. Note that
the planar-Rips complex induced by the six points in the above lemma is
nothing but the boundary complex of octahedron $\mathcal{O}_{2}$.

######  Theorem 3.15.

For any $n\geq 2$ and $X\subset\mathbb{R}^{2}$, if the planar-Rips complex
$\mathcal{R}(X)$ is an $n$-dimensional pseudomanifold then $\mathcal{R}(X)$ is
isomorphic to $\mathcal{O}_{n}$.

###### Proof.

We proceed by induction. Firstly, for the case when $n=2$, it follows from
Theorem 3.7 that $\mathcal{R}(X)$ is isomorphic to $\mathcal{O}_{2}$. Now let
$n>2$ and consider a strongly connected component of link of any $x\in X$, say
$\widetilde{\mathcal{O}}$. By induction, the subcomplex
$\widetilde{\mathcal{O}}$ is isomorphic to $\mathcal{O}_{n-1}$. From Lemma
3.9, the shadow $\mathcal{S}(\widetilde{\mathcal{O}})$ is a $2n$-sided convex
polygon.

######  Claim 1.

The point $x$ cannot be inside the polygon
$\mathcal{S}(\widetilde{\mathcal{O}})$

###### Proof.

On contrary, suppose $x$ is inside $\mathcal{S}(\widetilde{\mathcal{O}})$.
Then there exists an $(n-1)$-dimensional simplex $\Delta$ in
$\widetilde{\mathcal{O}}$ such that $x\in\mathrm{conv}((\Delta))$ . Since
$\mathcal{R}(X)$ is an $n$-dimensional pseudomanifold, the $(n-1)$-dimensional
simplex $\Delta$ is shared by exactly two $n$-dimensional simplices, one of
which is $\Delta\cup\left\\{x\right\\}$. Hence, there exists another point $y$
outside $\widetilde{\mathcal{O}}$ such that the vertices of $\Delta$ are
adjacent to $y$ i.e. $\Delta\cup\left\\{y\right\\}$ is an $n$-dimensional
simplex in $\mathcal{R}(X)$. Now from Lemma 2.6, we have $x\in Lk(y)$ i.e.
$\Delta\cup\left\\{x\right\\}\cup\left\\{y\right\\}$ is an $(n+1)$-dimensional
simplex. But this is not possible since $\mathcal{R}(X)$ is $n$-dimensional.

∎

Hence the point $x$ is outside the polygon
$\mathcal{S}(\widetilde{\mathcal{O}})$. Now we show that $x$ is a guard point
of polygon $\mathcal{S}(\widetilde{\mathcal{O}})$ along a side.

######  Claim 2.

There exists a side $ab$ of the polygon $\mathcal{S}(\widetilde{\mathcal{O}})$
such that $x$ is a guard point of $\mathcal{S}(\widetilde{\mathcal{O}})$ along
the side $ab$

###### Proof.

Figure 6. An illustration of the case when the ray $xP^{\rightarrow}$
intersects the side $cd$, and the intersection is outside the segment
$\overline{xP}$. This yields a $3$-simplex $\left\\{x,\tilde{P},c,d\right\\}$
containing the point $P$.

.

Using Lemma 3.10, it suffices to show that for every vertex $P$ of
$\mathcal{S}(\widetilde{\mathcal{O}})$, all the intersections of the ray
$xP^{\rightarrow}$ with $\mathcal{S}(\widetilde{\mathcal{O}})$ lies between
$x$ and $P$. On contrary, suppose there exists a vertex $P$ such that the
extension of ray $xP^{\rightarrow}$ intersects the polygon
$\mathcal{S}(\widetilde{\mathcal{O}})$, say at some edge $cd$ (See Figure 6).
Then we have $P\in\mathrm{conv}\left\\{x,c,d\right\\}$. Now consider the
antipodal point $\tilde{P}$ of $P$ in $\widetilde{\mathcal{O}}$ where the
points $x,c,d$ are adjacent to $\tilde{P}$ i.e. $\left\\{x,c,d\right\\}\subset
Lk(\tilde{P})$. Hence from Lemma 2.6, we have $P\in Lk(\tilde{P})$ i.e. the
points $P$ and $\tilde{P}$ are adjacent which is a contradiction.

∎

Now consider any $(n-1)$-dimensional simplex $\Delta$ in
$\widetilde{\mathcal{O}}$ which contains the vertices $a$ and $b$. Since
$\mathcal{R}(X)$ is an $n$-dimensional pseudomanifold, the $(n-1)$-dimensional
simplex $\Delta$ is shared by exactly two $n$-dimensional simplices, one of
which is $\Delta\cup\left\\{x\right\\}$. Hence, there exists another point $y$
outside $\widetilde{\mathcal{O}}$ such that the vertices of $\Delta$ are
adjacent to $y$ i.e. $\Delta\cup\left\\{y\right\\}$ is an $n$-dimensional
simplex in $\mathcal{R}(X)$. Note that $x$ and $y$ are non-adjacent since
otherwise $\Delta\cup\left\\{x,y\right\\}$ forms an $(n+1)$-simplex.

######  Claim 3.

The point $y$ is adjacent to all the vertices of $\widetilde{\mathcal{O}}$

###### Proof.

(a)

(b)

Figure 7. The points $x$ and $y$ are guard points of polygon
$\tilde{\mathcal{O}}$. The adjacency of $y$ with $\tilde{a}$ & $\tilde{b}$,
and $y$ being a guard point of polygon $\tilde{\mathcal{O}}$ along the side
$\overline{\tilde{a}\tilde{b}}$ prompts $y$ to be adjacent to every other
vertex of $\tilde{\mathcal{O}}$. On the right, the segments $\overline{ya}$
and $\overline{z\tilde{a}}$ intersect, implying adjacency between $y$ and $z$.

Firstly, the point $y$ is adjacent to $a$ and $b$. Now consider the antipodal
points $\tilde{a}$ and $\tilde{b}$ of $a$ and $b$ respectively. With the
points $a,b,\tilde{a},\tilde{b},x,y$, we are in the setting of Lemma 3.14 with
the parameter $r=1$, and the quadrilateral being $ab\tilde{a}\tilde{b}$. Hence
from Lemma 3.14, the point $y$ is adjacent to $\tilde{a}$ and $\tilde{b}$, and
is a guard point of quadrilateral $ab\tilde{a}\tilde{b}$ along the side
$\tilde{a}\tilde{b}$. The induced structure is illustrated in Figure 7(a).

Now let $z$ be any point of $\widetilde{\mathcal{O}}$ other than
$a,b,\tilde{a},\tilde{b}$. Since $y$ is a guard point of the quadrilateral
$ab\tilde{a}\tilde{b}$, either the segment $\overline{ya}$ intersects the
segment $\overline{z\tilde{a}}$ or the segment $\overline{yb}$ intersects the
segment $\overline{z\tilde{b}}$ in $\mathcal{S}(X)$, depending on whether the
point is on the left side or the right side of line $L_{xy}$ (For instance,
see Figure 7(b)). For both the cases, from Lemma 2.4, either $y$ or $z$ is an
apex since the antipodal points $a$ and $\tilde{a}$ or $b$ and $\tilde{b}$
cannot be adjacent i.e. $y$ is adjacent to $z$. ∎

Hence, the subcomplex spanned by $x$, $y$ and vertices of
$\widetilde{\mathcal{O}}$ is isomorphic to $\mathcal{O}_{n}$. Since the only
subcomplex of a pseudomanifold which is also a pseudomanifold of same
dimension is itself, the Rips complex $\mathcal{R}(X)$ is isomorphic to
$\mathcal{O}_{n}$..

∎

The above characterization of pseudomanifolds provides further insight into
the Rips complexes having a weak-pseudomanifold structure, where each strongly
connected component is a pseudomanifold, and the corresponding induced
subcomplex again inherits the planar-Rips structure.

######  Definition 3.16 (Iterated chain of $\mathcal{O}_{n}$s).

A finite $n$-dimensional simplicial complex $(n\geq 2)$ is said to be an
iterated chain of $\mathcal{O}_{n}$s if it can be expressed as the union
$\bigcup_{i=1}^{m}P_{i}$, where each $P_{i}$ is isomorphic to
$\mathcal{O}_{n}$, no three of them have a non-empty pairwise intersection,
and any two of them with non-empty intersection intersect

  1. (a)

at a single vertex when $n=2$.

  2. (b)

either at a single vertex or a single edge when $n>2$.

It can be easily checked that an iterated chain of $\mathcal{O}_{n}$s is a
weak-pseudomanifold, where each $P_{i}$ is a strongly connected component.

######  Proposition 3.17.

Let $K$ be an iterated chain of $\mathcal{O}_{n}$s, then $K$ is homotopy
equivalent to wedge sum of circles and $n$-spheres i.e.
$K\simeq\bigvee^{m}{\mathbb{S}^{n}}\vee\bigvee^{p}{\mathbb{S}^{1}}$ for some
$p\geq 0$, where $m=\\#$ of strongly connected components in $K$.

###### Proof.

Any two copies of $\mathcal{O}_{n}$ can share at most a single vertex or a
single edge. Further, any two $1$-simplices with a common vertex cannot be a
part of three distinct copies of $\mathcal{O}_{n}$. This allows for the
contraction of edges shared by two copies of $\mathcal{O}_{n}$, to a single
point upto homotopy, resulting in a chain of $n$-spheres $\mathbb{S}^{n}$
along the vertices. However, these spheres can be arranged in a cyclic
fashion, which gives rise to copies of circles in its homotopy type. ∎

######  Theorem 3.18.

Given $X\subset\mathbb{R}^{2}$, if the planar-Rips complex $\mathcal{R}(X)$ is
an $n$-dimensional weak-pseudomanifold then $\mathcal{R}(X)$ is isomorphic to
an iterated chain of $\mathcal{O}_{n}$s.

###### Proof.

Firstly, each strongly connected component is isomorphic to $\mathcal{O}_{n}$
since the corresponding induced subcomplex on each component inherits a
planar-Rips structure; denote the strongly connected components by
$\\{P_{i}\\}_{i=1}^{m}$. Now, suppose any two strongly connected components,
say $P_{i}$ and $P_{j}$ have a non-empty intersection, then their intersection
is a subcomplex of codimension at least $2$. Further, from Lemma 3.9, any
$k$-simplex ($k\geq 2$) in $P_{i}$ and $P_{j}$ is non-degenerate, and the
polygons $\mathcal{S}(P_{i})$ and $\mathcal{S}(P_{j})$ are convex; hence the
intersection $P_{i}\cap P_{j}$ is a vertex when $n=2$, and is either a vertex
or an edge when $n>2$.

Now from Lemma 2.5, no more than two strongly connected components can
intersect at a single vertex. Finally, it again follows from the convexity of
$\mathcal{S}(\mathcal{O}_{n})$ that any three $P_{i}$s cannot intersect
pairwise inside $\mathbb{R}^{2}$. ∎

######  Corollary 3.19.

If $\mathcal{R}(X)$ is an $n$-dimensional weak-pseudomanifold, then

$\mathcal{R}(X)\simeq\bigvee_{i=1}^{m}{\mathbb{S}^{n}}\vee\bigvee_{j=1}^{p}{\mathbb{S}^{1}}\
,$

for some $p\geq 0$, where $m=\\#$ of strongly connected components in
$\mathcal{R}(X)$.

Note that $p=0$ unless a subcollection of strongly connected components can be
arranged in a cyclic manner. Additionally, if $p\neq 0$ then $m>3$.

##  4\. Characterization of minimal $2$-cycles and two-dimensional closed
planar-Rips structures

In this section, we will prove C, laying the groundwork for recognizing two-
dimensional, pure and closed planar-Rips structures, a more general class of
$2$-pseudomanifolds. We will achieve this by first establishing its inherent
local structure and showing that a minimal 2-cycle admitting a planar-Rips
structure is isomorphic to $\mathcal{O}_{2}$.

######  Definition 4.1.

  * (a)

A finite $n$-dimensional pure simplicial complex is said to be closed if every
simplex of codimension $1$ has degree at least $2$ i.e. every $(n-1)$-simplex
is contained in at least two $n$-simplices.

  * (b)

A finite $n$-dimensional pure simplicial complex is said to be a minimal
$n$-cycle if the only subcomplex having $n^{th}$ homology of rank $1$ is
itself.

One can easily verify that minimal $n$-cycles are strongly connected and
closed.

######  Lemma 4.2.

For $X\subset\mathbb{R}^{2}$, if the planar-Rips complex $\mathcal{R}(X)$ is
an $n$-dimensional pure and closed simplicial complex ($n\geq 2$), then every
simplex is non-degenerate, meaning that no vertex in a simplex is contained
within the convex hull of its remaining vertices.

###### Proof.

Assume the contrary i.e. let there be a degenerate simplex, say $\sigma$ of
dimension at least $2$. Then there exists a vertex $v$ which is contained in
the convex hull of remaining vertices of $\sigma$. Let $\tau$ be a maximal
simplex containing $\sigma$ then $v\in\mathrm{conv}((\tau)-v)$. Since
$\mathcal{R}(X)$ is closed, there exists another $n$-simplex $\gamma$ that
does not contain $v$, such that $\gamma\neq\tau$ and $\tau-v\subset\gamma$.
Now from Lemma 2.6, $v\cup\gamma$ is an $(n+1)$-simplex in $\mathcal{R}(X)$
which is not possible. ∎

We will use the above proposition specifically for the case when $n=2$. This
proposition also implies that for a pure and closed two-dimensional planar-
Rips complex, the projection of each $n$-simplex in the shadow
$\mathcal{S}(X)$ is an $(n+1)$-sided convex polygon. Consider all those
$1$-simplices in $\mathcal{R}(X)$, whose projected interiors in the shadow
$\mathcal{S}(X)$ intersect the boundary of $\mathcal{S}(X)$. These
$1$-simplices will be referred to as boundary edges.

######  Definition 4.3 ($\gamma_{2}$-configuration).

A specific arrangement of four points in $\mathcal{R}(X)$ as an induced
subcomplex that contains exactly two $2$-simplices, such that the $1$-simplex
shared by two $2$-simplices lies on one side of the line joining the two non-
adjacent vertices.

Figure 8. $\boldsymbol{\gamma_{2}}$-configuration: The highlighted simplex (in
black) denotes the base of the configuration.

Additionally, the $1$-simplex shared between two $2$-simplices in the
$\gamma_{2}$-configuration will be referred to as the base of the
configuration. The following result is a simple consequence of Lemma 4.2.

######  Proposition 4.4.

In a finite two-dimensional, pure and closed planar-Rips complex
$\mathcal{R}(X)$,

  1. (i)

Every boundary edge is a base of some $\gamma_{2}$-configuration.

  2. (ii)

If two edges intersect at their projected interiors, then they induce a
$\gamma_{2}$-configuration.

###### Proof.

Since $\mathcal{R}(X)$ is closed, consider any two $2$-simplices containing
the boundary edge; their projected interiors intersect in the shadow
$\mathcal{S}(X)$. There are two possibilities: either one of the two simplices
is degenerate or they together form a $\gamma_{2}$-configuration. However,
from Lemma 4.2, both the simplices are non-degenerate. This proves $(i)$.

(a)

(b)

(c)

Figure 9. Illustration of all possible and forbidden cases in the proof of
Proposition 4.4$.(ii)$.

For (ii), suppose $[AD]$ and $[BC]$ are two edges in $\mathcal{R}(X)$ whose
projected interiors intersect. From Lemma 2.4, assume without loss of
generality that the vertex $B$ is adjacent to both $A$ and $D$ as illustrated
in Figure 9(a). Now it suffices to show that the vertex $C$ is either adjacent
to $A$ or $D$. Note that $C$ cannot be adjacent to both $A$ and $D$ since
$\mathcal{R}(X)$ is two-dimensional. Further from Lemma 4.2, no three vertices
of $A,B,C,D$ are collinear.

On contrary, suppose $C$ is neither adjacent to $A$ nor $D$. Since
$\mathcal{R}(X)$ is closed, a vertex $P\in X$ exists which is adjacent to both
$A$ and $D$, but not adjacent to $B$. It now follows from Lemma 3.13 that
$C\in\mathrm{conv}\left\\{A,D,P\right\\}$, as shown in Figure 9(b).
Consequently, $C$ is adjacent to both $A$ and $D$ which is absurd.

∎

######  Corollary 4.5.

Every finite two-dimensional, pure and closed planar-Rips complex
$\mathcal{R}(X)$ contains a $\gamma_{2}$-configuration.

Note that the above proposition is an extended version of Lemma 2.4 for the
case when $\mathcal{R}(X)$ has a two-dimensional, pure and closed simplicial
structure. Here, any two segments when they intersect, precisely yield a
$\gamma_{2}$-configuration.

######  Lemma 4.6.

Let $\mathcal{R}={\left\langle{ABCD}\right\rangle}$ be a
$\gamma_{2}$-configuration containing the simplices $[ABC]$ and $[ABD]$ such
that the points $C$ and $D$ are non-adjacent, and the segments $\overline{AD}$
and $\overline{BC}$ intersect. Then $\phase{CAB}+\phase{ABD}>180^{\circ}$ i.e.
at least one of $\phase{CAB}$ or $\phase{ABD}$ is obtuse.

###### Proof.

This simply follows with the argument that the length of side $\overline{CD}$
is larger than the diagonal lengths $\overline{AD}$ and $\overline{BC}$ in the
quadrilateral $ABDC$. ∎

Now we show that every closed two-dimensional planar-Rips complex has a copy
of $\mathcal{O}_{2}$ as an induced subcomplex. The strategy employed is to use
the ‘closed’ness property of $\mathcal{R}(X)$ to add two more vertices along
with the $\gamma_{2}$-configuration, and then use the proximity relations on
these six vertices to establish the precise adjacency, proving that the
induced subcomplex on these six vertices is isomorphic to $\mathcal{O}_{2}$.

######  Theorem 4.7.

For any $X\subset\mathbb{R}^{2}$, if the planar-Rips complex $\mathcal{R}(X)$
is a two-dimensional pure and closed simplicial complex then $\mathcal{R}(X)$
has an induced subcomplex isomorphic to $\mathcal{O}_{2}$. Hence, the second
Betti number $b_{2}(\mathcal{R}(X))$ is non-zero.

###### Proof.

We will repeatedly use Proposition 4.4.$(ii)$ to prove this theorem. Firstly,
as follows from this proposition, we start by taking a
$\gamma_{2}$-configuration, say ${\left\langle{ABCD}\right\rangle}$ as an
induced subcomplex in $\mathcal{R}(X)$ where the simplices $[ABC]$ and $[ABD]$
are in $\mathcal{R}(X)$, the points $C$ and $D$ are non-adjacent, and the
segments $\overline{AD}$ and $\overline{BC}$ intersect. Note that the points
$C$ and $D$ are on the same side of the line $L_{AB}$ i.e. without loss of
generality, assume $C,D\in L^{+}_{AB}$.

Now, since $\mathcal{R}(X)$ is closed, there exists at least another point for
each of $[AD]$ and $[BC]$, say $P$ and $Q$ respectively, such that the two
simplices $[ADP]$ and $[BCQ]$ are in $\mathcal{R}(X)$. Note that $P\neq Q$ and
the points $A$ and $Q$ are non-adjacent since $\mathcal{R}(X)$ is two-
dimensional. Likewise, the points $B$ and $P$ are non-adjacent. Hence, the
point $P$ lies on the same side of the line of perpendicular bisector
$L_{A|B}$ as $A$ does i.e. $P\in L^{+}_{A|B}$ and the point $Q$ lies on the
same side of $L_{A|B}$ as $B$ does i.e. $Q\in L^{-}_{A|B}$. Using Lemma 4.6,
we also assume without loss of generality that $\phase{CAB}$ is obtuse.

######  Claim 1.

The points $C$ and $D$ lie on either side of the bisector $L_{A|B}$.

###### Proof.

Figure 10. An illustration of 1. When $\mathcal{R}(X)$ is closed, $C$ and $D$
lie on same side of the bisector $L_{A|B}$, which is possile only when $C$ and
$D$ are adjacent

.

Let if possible, both $C$ and $D$ be on the same side of line $L_{A|B}$ i.e.
let $C,D\in L^{+}_{A|B}$(since $\phase{CAB}$ is obtuse). Consider the set
$L^{-}_{A|B}\cap L^{+}_{C|A}$; the point $Q$ being closer to $B$ and $C$ than
$A$ implies $Q\in L^{-}_{A|B}\cap L^{+}_{C|A}$. This is illustrated in Figure
10. Hence from Lemma 3.13, $D\in\mathrm{conv}\left\\{B,C,Q\right\\}$ i.e. $C$
and $D$ are adjacent which is not true.

∎

Hence, $C\in L^{+}_{A|B}$ and $D\in L^{-}_{A|B}$. With the above inference
about points $C$ and $D$, it is possible to draw further conclusion about the
specific region in which points $P$ and $Q$ should lie.

######  Claim 2.

$P,\ Q\in L^{+}_{AD}\cap L^{-}_{BC}$.

###### Proof.

(a) $P\in L^{+}_{A|B}\cap\ cl(L^{+}_{BC})\cap L^{-}_{DC}$

(b) $P\in L^{+}_{A|B}\cap\ cl(L^{+}_{BC})\cap L^{+}_{DC}$

Figure 11.  An illustration of proof of 2: For a $\gamma_{2}$-configuration
${\left\langle{ABCD}\right\rangle}$, the two regions are illustrated where
point $P$ cannot lie.

We have $P\in L^{+}_{A|B}$. Now for any point $Z\in L^{+}_{A|B}\cap\
cl(L^{+}_{BC})$, there are two possibilities:

  1. (a)

If $Z\in L^{-}_{DC}$ then $C\in conv\left\\{A,D,Z\right\\}$ (Lemma 3.12).

  2. (b)

If $Z\in L^{+}_{DC}$ then the segments $\overline{ZD}$ and $\overline{BC}$
intersect and from Proposition 4.4.$(ii)$, $Z$ is adjacent to $B$, since $C$
and $D$ are non-adjacent.

In particular, if $P\in L^{+}_{A|B}\cap(L_{BC}\cup L^{+}_{BC})$ then either
$C$ is adjacent to $D$ or $P$ is adjacent to $B$, neither of which is true.
This is illustrated with an example in Figure 11(a) and Figure 11(b). Hence,
$P\in L^{-}_{BC}$. With analogous arguments, $Q\in L^{+}_{AD}$. Since $P\in
L^{+}_{A|B}\cap L^{-}_{BC}\subset L^{+}_{AD}$ and $Q\in L^{-}_{A|B}\cap
L^{+}_{AD}\subset L^{-}_{BC}\ $, therefore $P,\ Q\in L^{+}_{AD}\cap
L^{-}_{BC}$.

∎

(a)

(b)

Figure 12.  On the left, the intersection of segments (in black) in each case
is possible since $P,Q\in L^{+}_{AD}\cap L^{-}_{BC}$. On the right, the final
induced complex obtained is isomorphic to $\mathcal{O}_{2}$

Now it remains to show that $P$ and $Q$ are adjacent, and both are adjacent to
$C$ and $D$ which proves that the induced subcomplex
${\left\langle{ABCDPQ}\right\rangle}$ is isomorphic to $\mathcal{O}_{2}$.
Consider the line segments $\overline{PD}$ and $\overline{QC}$; From the above
observations about the region where points $P$ and $Q$ lie, the line segments
$\overline{PD}$ and $\overline{QC}$ intersect since $P\notin
conv\left\\{B,C,Q\right\\}$ and $Q\notin conv\left\\{A,D,P\right\\}$.
Likewise, the line segments $\overline{PA}$ and $\overline{QC}$ intersect, and
the line segments $\overline{PD}$ and $\overline{QB}$ intersect. Along with
this, the pairs $\left\\{A,Q\right\\}$, $\left\\{B,P\right\\}$, and
$\left\\{C,D\right\\}$ are non-adjacent pairs of vertices (See Figure 12).
Therefore it follows from Proposition 4.4.$(ii)$ that the points $P$ and $Q$
are adjacent, points $P$ and $C$ are adjacent, and points $Q$ and $D$ are
adjacent. This concludes the proof.

∎

######  Corollary 4.8.

For $X\subset\mathbb{R}^{2}$, if $\mathcal{R}(X)$ is a minimal $2$-cycle then
it is isomorphic to $\mathcal{O}_{2}$.

######  Remark 4.9.

Theorem 3.15 for $n=2$ case is now simply a consequence of Theorem 4.7 since a
pseudomanifold is a minimal cycle. In general, we like to know if Theorem 4.7
can be extended even for higher dimensions.

######  Question 4.10.

Suppose $\mathcal{R}(X)$ is a minimial $n$-cycle, then is it isomorphic to
$\mathcal{O}_{n}$?

The proof of Theorem 4.7 has a further implication that in a two-dimensional,
pure and closed Rips complex, every $\gamma_{2}$-configuration further extends
to $\mathcal{O}_{2}$, and is contained in precisely one copy of
$\mathcal{O}_{2}$ in $\mathcal{R}(X)$. Hence, every $\gamma_{2}$-configuration
is a part of precisely one non-trivial homology $2$-cycle. This further leads
us to characterize all two-dimensional, pure and closed Rips complexes by
considering the projection map $p:\mathcal{R}(X)\to\mathcal{S}(X)$.

######  Lemma 4.11.

In a finite, two-dimensional, pure and closed planar-Rips complex
$\mathcal{R}(X)$, the projection of every boundary edge is completely
contained in the boundary of $\mathcal{S}(X)$.

###### Proof.

Suppose not, then there exists two boundary edges in $\mathcal{R}(X)$, say
$[AB]$ and $[CD]$ whose projected interiors intersect in the shadow
$\mathcal{S}(X)$ with $B$ and $C$ being non-adjacent. Now it follows from
Proposition 4.4$.(i)$ that the induced subcomplex
${\left\langle{ABCD}\right\rangle}$ is a $\gamma_{2}$-configuration, which
further extends to $\mathcal{O}_{2}$ as shown in Theorem 4.7. But this is not
possible since $[AB]$ and $[CD]$ are boundary edges in $\mathcal{R}(X)$.

∎

######  Proposition 4.12.

A two-dimensional, pure and closed Rips complex $\mathcal{R}(X)$ with
$b_{2}(\mathcal{R}(X))=1$ is isomorphic to $\mathcal{O}_{2}$.

###### Proof.

Since $\mathcal{R}(X)$ contains a copy of $\mathcal{O}_{2}$ as an induced
subcomplex, it suffices to show that there does not exist any other
$2$-simplex outside or on the boundary edges of the induced subcomplex
$\mathcal{O}_{2}$. But this follows from Proposition 4.4 and Lemma 4.11. ∎

######  Remark 4.13.

For the planar-Rips structure of boundary complex of octahedron
$\mathcal{O}_{2}$, consider its shadow $\mathcal{S}(\mathcal{O}_{2})$ which is
a convex hexagon under the projection map $p:\mathcal{R}(X)\to\mathcal{S}(X)$.
Then $p$ is injective on the boundary of $\mathcal{O}_{2}$, and the inverse
image of every point in the interior of hexagon $\mathcal{S}(\mathcal{O}_{2})$
has exactly two points in $\mathcal{O}_{2}$. More generally, it simply follows
from Lemma 4.2 and Proposition 4.4.$ii$ that for a $2$-dimensional pure and
closed Rips complex $\mathcal{R}(X)$, the inverse image of every point in the
shadow $\mathcal{S}(X)$ has at most two points in $\mathcal{R}(X)$.
Alternatively from an algorithmic perspective, each copy of $\mathcal{O}_{2}$
can be identified as the tripartite graph $K_{2,2,2}$ (See Section 5.1) in the
graph of $1$-skeleton $\mathcal{R}^{(1)}(X)$.

######  Proposition 4.14.

In a finite, two-dimensional, pure and closed planar-Rips complex
$\mathcal{R}(X)$, denote $S$ to be set of all points in the shadow
$\mathcal{S}(X)$ whose inverse image under the projection map
$p:\mathcal{R}(X)\to\mathcal{S}(X)$ has exactly two points. Then

  1. (i)

$b_{2}(\mathcal{R}(X))=b_{0}(S)$ i.e. the second Betti number
$b_{2}(\mathcal{R}(X))$=# connected components in $S$. More specifically,
$b_{0}$=Number of cycles of length $6$ in $\mathcal{R}(X)$ which has at least
two of its diagonals intersecting at their interiors.

  2. (ii)

$\mathcal{R}(X)$ has exactly $b_{2}(\mathcal{R}(X))$ copies of
$\mathcal{O}_{2}$ as induced subcomplex.

###### Proof.

Suppose $T$ is any connected component of $S$, then there exists two edges in
$\mathcal{R}(X)$ whose projected interiors intersect in $T$. Hence from
Proposition 4.4.$ii$, the two edges induce a $\gamma_{2}$-configuration, and
from Theorem 4.7, this configuration further extends to an induced subcomplex
of $\mathcal{O}_{2}$. Since the projected interior of the hexagon
$\mathcal{S}(\mathcal{O}_{2})$ is connected,
$\mathcal{S}(\mathcal{O}_{2})\subseteq T$. However, the map $p$ is injective
on the boundary edges of $\mathcal{O}_{2}$ which implies
$T=\mathcal{S}(\mathcal{O}_{2})$ i.e. every connected component of $S$
corresponds to an induced subcomplex of $\mathcal{O}_{2}$ in $\mathcal{R}(X)$.
Hence, $b_{2}(\mathcal{R}(X))\geq b_{0}(S)$. Further, since any minimal
$2$-cycle in $\mathcal{R}(X)$ is isomorphic to $\mathcal{O}_{2}$ (Corollary
4.8), it follows that $b_{2}(\mathcal{R}(X))=b_{0}(S)$. This proves (i). Now
(ii) is a direct consequence of (i).

∎

##  5\. Obstructions to planar-Rips complexes and correlations with Unit Disk
Graphs

In this section, we introduce the concept of obstructions to planar-Rips
complexes, an area that remains unexplored in literature. However, it’s worth
noting that the idea of ‘obstructions’ is not entirely novel [21, 22]. Armed
with a comprehensive list of forbidden planar-Rips structures, we present a
few examples that illustrate a potential framework for extracting obstructions
to planar-Rips complex from these forbidden structures.

We begin with unifying the study of planar-Rips complexes and unit disk graphs
by establishing a one-to-one correspondence between both the categories. The
functors that facilitate this correspondence are “taking clique complex” and
“taking $1$-skeleton”, which transform a unit disk graph to a planar-Rips
complex and vice versa, respectively. This paves the way to retrieve the known
obstructions to planar-Rips complexes in terms of their graph counterpart,
called minimal non unit disk graphs. Additionally, we consolidate our findings
on the classification of planar-Rips complexes from previous sections in terms
of unit disk graphs, proving D.

######  Definition 5.1 (Unit disk graph).

A graph where each vertex represents a point in the Euclidean plane and an
edge is drawn between two points if the distance between two points is less
than a fixed threshold $r>0$.

Planar-Rips complexes are flag complexes that exhibit a key property: the
clique complex of the graph of its $1$-skeleton is same as the original
complex. It is easy to see that every unit disk graph can be identified as the
$1$-skeleton of a planar-Rips complex. In fact, the following equivalence can
be inferred.

######  Proposition 5.2.

Given any finite set $X\subset\mathbb{R}^{2}$, the planar-Rips complex of $X$
is same as the clique complex of the unit disk graph, having the vertex set as
$X$.

For simplicity, we shall fix $r=1$ given the scale-invariant nature of our
study. Hence, for $X\subset\mathbb{R}^{2}$, we shall denote the unit disk
graph on the vertex set $X$ by $\mathcal{R}^{1}(X)$, which denotes the
$1$-skeleton of planar-Rips complex.

Consequently, there is a one-to-one correspondence, implying that both the
categories are isomorphic. This correspondence facilitates the integration of
both studies, enabling the translation of the statements and results in the
category of planar-Rips complexes into corresponding analogs for the category
of unit disk graphs, or vice-versa.

In the preceding sections, a complete characterization of planar-Rips
complexes with $n$-dimensional weak-pseudomanifold structure and minimal
$2$-cycle structure has been outlined, including a partial characterization of
two-dimensional, pure, and closed planar-Rips complexes. These structures
correspond to unit disk graphs having all maximal cliques of size $(n+1)$, and
every clique of size $n$ being a part of exactly two maximal cliques.
Furthermore, a relation can be drawn for unit disk graphs corresponding to the
property of ’strongly connected’ness of planar-Rips complexes. To make these
characterizations readily accessible in terms of unit disk graphs, we redefine
some graph analogs corresponding to pseudomanifolds, weak-pseudomanfolds and
closed simplicial complexes:

######  Definition 5.3.

  1. (a)

A clique is said to be maximal if it is not contained in a clique of larger
size.

  2. (b)

A graph is said to be pure if all its maximal cliques are of same size.

  3. (c)

A pure graph (with clique number $n$) is said to be strongly connected if for
any two maximal cliques $\sigma\text{ and }\gamma$, there exists a sequence of
maximal cliques, say $\lambda_{1},\lambda_{2},\dots\lambda_{k},$ such that
$\lambda_{1}=\sigma,\ \lambda_{k}=\gamma$ and $\lambda_{i}\cap\lambda_{i+1}$
is a clique of size $(n-1)$ for all $1\leq i\leq k-1$.

  4. (d)

A pure graph (with clique number $n$) is said to be closed if every clique of
size ($n-1$) is contained in at least two maximal cliques.

Note that the graph of $1$-skeleton of a simplicial complex can be pure
although the simplicial complex need not be pure. A simple example to
illustrate this is the complex $\Delta_{2}\sqcup\partial\Delta_{2}$, where
$\Delta_{2}$ is a $2$-simplex and $\partial\Delta_{2}$ represents the boundary
of $2$-simplex. However, in case of flag complexes, it can be easily checked
that a flag complex is pure if and only if the graph of its $1$-skeleton is
pure. More specifically, a unit disk graph is pure if and only if the
corresponding planar-Rips complex is pure.

###  5.1. Graph of cross-polytopes:

Reframe these statements for my research paper : ”The class of planar-Rips
complexes have an ability to be characterized by the forbidden planar-Rips
structures. This section is specifically streamlined towards exploring this
fascinating feature of class of planar-Rips complexes.”

The graph of cross-polytopes appears most often as the induced subcomplex in
pure and strongly connected unit disk graphs (See Corollary 5.4). The graph of
$1$-skeleton of the boundary complex of an $n$-dimensional cross-polytope is
isomorphic to a complete $n$-partite graph with each independent set of size
$2$. For instance, the graph of octahedron is isomorphic to the complete
tripartite graph $K_{2,2,2}$ (See Figure 13.) Henceforth, we shall also refer
to these graph as complete bi-independent $n$-partite graph. We will denote
this graph by $K_{n\times 2}$ as defined by Brouwer et al. [10, p. 478], to
mean the complete $n$-partite graph $K_{\underbrace{2,2,\dots,2}_{n\text{
times}}}$.

Figure 13. Complete bi-independent $3$-partite graph $K_{2,2,2}$

Now we will state some of the corollaries which are natural graph analogs to
the theorems proved in the previous sections. These corollaries reveal
interesting properties of unit disk graph structures, demonstrating the power
and generality of our approach, and open up new avenues for our further study
on forbidden structures for planar-Rips complexes and unit disk graphs:

######  Corollary 5.4.

Let $G$ be a pure and closed unit disk graph with $\omega(G)=3$ then

  1. (i)

$G$ contains an induced subgraph isomorphic to $K_{2,2,2}$.

  2. (ii)

Given two edges $e_{1}$ and $e_{2}$ intersecting at their interiors, there
exists precisely one copy of $K_{2,2,2}$ as induced subgraph that contains
$e_{1}$ and $e_{2}$.

  3. (iii)

Any induced subgraph $K_{2,2,2}$ in $G$ has a non-planar configuration(as
shown in Figure 13), containing six pairs of intersecting edges.

  4. (iv)

There are precisely $\frac{k}{6}$ distinct copies of $K_{2,2,2}$ as induced
subgraphs where $k$ is the number of pairs of intersecting edges

###### Proof.

These simply follow from Theorem 4.7, Proposition 4.4, Remark 4.13, and
Proposition 4.14 by considering the graph of $1$-skeleton of two-dimensional
pure and closed planar-Rips complexes. ∎

######  Remark 5.5.

For the above theorem, it is easy to verify that a graph $G$ is pure and
closed with clique number $\omega(G)=3$ if and only if $G$ is connected with
$\omega(G)=3$, as stated in D, where every edge has a degree of at least $2$.

######  Corollary 5.6.

For $n\geq 3$, suppose $G$ is a pure unit disk graph with $\omega(G)=(n+1)$,
and every clique of size $n$ is contained in exactly two maximal cliques. Then
$G$ is isomorphic to the $1$-skeleton of an iterated chain of
$\mathcal{O}_{n}$s. More precisely, up to isomorphism, $G$ can be written as
$\cup_{i=1}^{m}H_{i}$, where each $H_{i}$ is isomorphic to $K_{n\times 2}$, no
three of them have a non-empty pairwise intersection, and any two of them with
non-empty intersection, intersect

  1. (1)

at a single vertex when $n=2$.

  2. (2)

either at a single vertex or a single edge when $n>2$.

###### Proof.

This simply follows from Theorem 3.18 by considering the graph of $1$-skeleton
of planar-Rips complexes with weak-pseudomanifold structure. ∎

###  5.2. Obstructions to Planar-Rips complexes

Given a hereditary property $\mathcal{P}$ in the category of simplicial
complexes or the category of graphs, any complex or a graph that does not
satisfy $\mathcal{P}$ further contains a minimal induced substructure, say
$F$, that does not satisfy $\mathcal{P}$. The minimality is defined such that
all the induced substructures of $F$ do satisfy $\mathcal{P}$. The existence
of such an $F$ can be easily verified with repetitive vertex deletions. In
case of simplicial complexes, these structures are referred to as obstructions
to the corresponding property. We will now define obstructions to planar-Rips
complexes, where the property $\mathcal{P}$ denotes whether the simplicial
complex admits a planar-Rips structure.

######  Definition 5.7.

An obstruction to planar-Rips complex is a simplicial complex that does not
admit planar-Rips structure, all of whose proper induced subcomplexes do.

We say a graph $G$ admits a unit disk graph structure if there exists an
injective map $f:V(G)\to\mathbb{R}^{2}$ such that $G$ is isomorphic to the
unit disk graph $\mathcal{R}^{1}(f(V))$. In other words, $uv$ is an edge if
and only if the distance between $f(u)$ and $f(v)$ is less than $1$. In case
of unit disk graphs, the analog of obstructions are minimal forbidden induced
subgraphs for unit disk graphs, referred to as minimal non unit disk graphs
[4].

######  Definition 5.8.

A graph $G$ is said to be a minimal non unit disk graph (minimal non-UDG) if
every induced subgraph of $G$ other than $G$ itself admits a unit disk graph
structure.

There is a close relationship between the minimal non-UDGs and the
obstructions to planar-Rips complexes. The following is a straightforward
inference:

######  Claim.

The clique complex of a minimal forbidden induced subgraph for unit disk graph
is an obstruction to planar-Rips complex.

However, it is not true that the $1$-skeleton of every obstruction to planar-
Rips complex is a minimal forbidden induced subgraph for unit disk graph. For
instance, the boundary complex of all $n$-dimensional simplices are
obstructions to planar-Rips complex. Considering that these are also the
obstructions to flag complexes, therefore, we shall restrict only to the class
of flag complexes to have the one-to-one correspondence as follows:

######  Proposition 5.9.

Let $K$ be a flag complex, then $K$ is an obstruction to planar-Rips complex
if and only if the graph of $1$-skeleton $K^{(1)}$ is a minimal non-UDG.

###### Proof.

This is simply a direct consequence of Proposition 5.2. ∎

Therefore, it follows that the clique complex of a minimal non-UDG is an
obstruction to planar-Rips complex. The literature on minimal non-UDGs is
surprisingly sparse despite active research in unit disk graphs. The following
theorem provides a concise summary of currently known minimal non-UDGs from
[4, 5], providing us with a few obstructions to planar-Rips complex.

$G_{2}$$G_{7}$$G_{6}$$G_{5}$$G_{4}$$G_{3}$$G_{1}$ Figure 14. Known minimal non
unit disk graphs with $5$, $6$ and $7$ vertices (Source: [5, p. 2])

######  Theorem 5.10.

The following graphs are minimal non-UDGs. More precisely, the clique complex
of these graphs are obstructions to planar-Rips complex.

  1. (1)

Graphs in Figure 14

  2. (2)

$\overline{K_{2}+C_{2k+1}}$ for every $k\geq 1$

  3. (3)

$\overline{C_{2k}}$ for every $k\geq 4$

  4. (4)

$C^{*}_{2k}$ for every $k\geq 4$

Note that in the above theorem, the graph $C^{*}_{2k}$ denotes the graph
obtained by adding two $k$-cliques $\overline{U}$ and $\overline{V}$ to the
cyclic graph $C_{2k}$, where $U$ and $V$ are the two maximal independent sets
in $C_{2k}$, each of size $k$. Furthermore, it follows that there is an
obstruction to planar-Rips complex in every odd dimension $d$.

In the realm of topology, the classification problem, namely, classification
of structures like manifolds, pseudomanifolds and weak-pseudomanifolds up to
homeomorphism (or homotopy) has been extensively studied and still remains a
hot topic. Indeed, these structures have been largely classified in the
literature. Following Theorem 2.3, Theorem 4.7 and Lemma 3.6, we have a large
class of forbidden induced structures for planar-Rips complexes and unit disk
graphs. For instance, the result by Adamszek in Theorem 3.3 implies that no
manifold other than the cross-polytopal spheres $\mathcal{O}_{n}$ admits a
planar-Rips structure. This makes a pavement for extracting a wide spectrum of
obstructions from these forbidden structures. Consider the following examples.

######  Example 5.11.

Let $K$ be the complex $C_{5}*\mathbb{S}^{0}$, a flag triangulation of sphere
$\mathbb{S}^{2}$ where $C_{5}$ is a cycle of length $5$. The complex $K$ being
a $2$-dimensional pseudomanifold does not admit a planar-Rips structure as
follows from Theorem 3.7. But is the complex $K$ an obstruction to planar-Rips
complex? The $1$-skeleton of $K$ can be identified as the complement of the
graph $\overline{K_{2}+C_{5}}$ which is a minimal non-UDG as shown in [5,
Theorem 4.1]. Therefore, the complex $K$ is indeed an obstruction to the
planar-Rips complex.

ICAHKDEJGFBCIKHJ (a) Minimal flag triangulation of $\mathbb{R}P^{2}$

AGBFCDE (b) Graph of $1$-skeleton of ${\left\langle{ABCDEFG}\right\rangle}$

Figure 15. Representation of minimal flag triangulation of $\mathbb{R}P^{2}$
in terms of its $1$-skeleton (on the left) that does not admit a planar-Rips
structure. Its induced subcomplex ${\left\langle{ABCDEFG}\right\rangle}$ (on
the right) is an obstruction to planar-Rips complex

######  Example 5.12.

Consider the minimal triangulation of the projective space $\mathbb{R}P^{2}$
with $11$ vertices as shown in Figure 15(a) [12, Example 3.1]. We know that
this complex does not admit a planar-Rips structure since its fundamental
group is not free. Hence, there exists at least one obstruction to planar-Rips
complex that is embedded inside this triangulation. The complex being non-
orientable and with a torsion in its homology group, it appears to be a
‘highly forbidden’ structure for a planar-Rips complex, meaning that an
embedded obstruction should be repetitive in its structure. With this said, we
consider the induced subcomplex $K={\left\langle{ABCDEFG}\right\rangle}$ and
consequently prove in the next theorem that the graph of $1$-skeleton of $K$
is a minimal non-UDG. In other words, $K$ is indeed an obstruction to planar-
Rips complex.

######  Theorem 5.13.

The graph in Figure 15(b) is a minimal non-UDG, or equivalently, its clique
complex is an obstruction to planar-Rips complex.

###### Proof.

Let $K={\left\langle{ABCDEFG}\right\rangle}$ denote the clique complex of the
graph in Figure 15(b). We first show that $K$ does not admit a planar-Rips
structure. On contrary, suppose it admits a planar-Rips structure; Without
loss of generality, let $\mathcal{R}(X)$ denote the planar-Rips structure,
where $X=\left\\{A,B,C,D,E,F,G\right\\}\subset\mathbb{R}^{2}$. Note that the
fundamental group $\pi_{1}(\mathcal{R}(X))$ is non-trivial.

(a)

(b)

Figure 16.  Two possible configurations of
${\left\langle{BCDEFG}\right\rangle}$, illustrating that $\overline{CB}$ lies
in the interior of polygon $DCEFBG$.

######  Claim.

The line segment
$\overline{CB}\in\mathrm{conv}\left\\{C,D,E\right\\}\cup\mathrm{conv}\left\\{D,E,F,B,G\right\\}$

###### Proof.

Consider the line $L_{CB}$ and the perpendicular bisectors $L_{C|B},L_{D|C}$,
and $L_{C|E}$. Firstly, $E$ cannot be on the line $L_{CB}$ since $E$ is not
adjacent to $B$, and $C$ is not adjacent to $F$. Likewise, $D$ cannot be on
the line $L_{CB}$. Without loss of generality, assume $E$ is on the right side
of the line $L_{CB}$ i.e. $E\in L^{-}_{CB}$. Considering the adjacency between
the vertices, we have the following observations:

  1. (a).

$D,E\in L^{+}_{C|B}$ and $F,G\in L^{-}_{C|B}$

  2. (b).

$B\in L^{+}_{C|E}$ and $F\in L^{-}_{C|E}$

  3. (c).

$B\in L^{-}_{D|C}$ and $G\in L^{+}_{D|C}$

  4. (d).

$E$ and $F$ are on same side of line $L_{CB}$

  5. (e).

$D$ and $G$ are on same side of line $L_{CB}$

If suppose $D,G\in L^{-}_{CB}$. Since non-adjacent vertices $F$ and $G$ are
adjacent to $B$, we have $G\in L^{+}_{B|F}$ and $F\in L^{+}_{B|G}$. But in
contrast, this is not possible unless $F$ and $G$ are adjacent. Hence, $D,G\in
L^{+}_{CB}$.

With this arrangement of vertices, the segment $\overline{CB}$ lies on the
left side of every line joining any two adjacent vertices of polygon $DCEFBG$
(in counterclockwise order). See Figure 16 for an illustration. It follows
that
$\overline{CB}\in\mathrm{conv}\left\\{C,D,E\right\\}\cup\mathrm{conv}\left\\{D,E,F,B,G\right\\}$.
∎

Consequently, the shadow $\mathcal{S}(X)$ is contractible since
${\left\langle{ABDEFG}\right\rangle}$ is a cone over vertex $A$. In
particular, $\pi_{1}(\mathcal{R}(X))$ is trivial as follows from Theorem 2.3.
This is a contradiction. Therefore, the complex $K$ does not admit a planar-
Rips structure.

Additionally, it can be easily verified that every induced subcomplex of $K$
admits a planar-Rips structure. Therefore, $K$ is an obstruction to planar-
Rips complex. ∎

Note that the minimal non-UDG in Figure 15(b) is a spanning subgraph of
$\overline{K_{2}+C_{5}}$, which is also a minimal non-UDG (see Example 5.11).
In particular, the class of Unit Disk graphs need not be hereditary under edge
deletion.

##  6\. Concluding remarks

In a combinatorial framework, the topological methods stand out for their
robust ability to uncover locally governed features that are pivotal for
reconstructing the global structure. The methods and results presented in this
paper highlight the effectiveness of topological and geometric approaches
towards characterizing planar-Rips complexes by capturing the local
constraints. In particular, the concept of obstructions to planar-Rips
complexes has been introduced, a tool that can aid in recognizing forbidden
planar-Rips structures. Notably, this concept has a natural generalization to
Vietoris-Rips complexes inside any metric space. It is also worth noting that
the challenge of determining the obstructions to planar-Rips complexes can be
reformulated into the following problem:

######  Problem 6.1.

Given a flag complex $K$ that does not admit a planar-Rips structure, devise
methodologies to determine the induced subcomplex(es) of $K$ that are
obstructions to planar-Rips complex.

Developing algorithms for recognizing forbidden planar-Rips complexes presents
another significant avenue for research. It would be interesting to know how
far this approach can be developed. Moreover, our work progresses towards
proving the conjecture [2] that every planar-Rips complex is homotopy
equivalent to a wedge of spheres.

## References

  * [1] Chambers, Erin & Silva, Vin & Erickson, Jeff & Ghrist, Robert. (2010). Vietoris–Rips Complexes of Planar Point Sets. Discrete & Computational Geometry. 44. 75-90. 10.1007/s00454-009-9209-8.
  * [2] Adamaszek, Michal & Frick, Florian & Vakili, Adrien. (2017). On Homotopy Types of Euclidean Rips Complexes. Discrete & Computational Geometry. 58. 10.1007/s00454-017-9916-5.
  * [3] Adamaszek, Michal & Adams, Henry. (2015). The Vietoris-Rips complexes of a circle. Pacific Journal of Mathematics. 290. 10.2140/pjm.2017.290.1.
  * [4] Marathe, Madhav V., Heinz Breu, Harry B. Hunt, S. S. Ravi and Daniel J. Rosenkrantz. “Simple heuristics for unit disk graphs.” Networks 25 (1995): 59-68.
  * [5] Atminas, Aistis & Zamaraev, Victor. (2018). On Forbidden Induced Subgraphs for Unit Disk Graphs. Discrete & Computational Geometry. 60. 10.1007/s00454-018-9968-1.
  * [6] Clark BN, Colbourn CJ, Johnson DS. Unit disk graphs. Discrete Mathematics. 1990 Dec 14;86(1-3):165-177. doi: 10.1016/0012-365X(90)90358-O
  * [7] A. Vergne, L. Decreusefond and P. Martins, ”Reduction algorithm for simplicial complexes,” 2013 Proceedings IEEE INFOCOM, Turin, Italy, 2013, pp. 475-479, doi: 10.1109/INFCOM.2013.6566818.
  * [8] Banagl, Markus & Friedman, Greg. (2004). Triangulations of 3-dimensional pseudomanifolds with an application to state-sum invariants, Algebr. Algebraic & Geometric Topology. 4. 10.2140/agt.2004.4.521.
  * [9] Ghosh, Subir Kumar. Visibility Algorithms in the Plane. Cambridge: Cambridge University Press, 2007. doi:10.1017/CBO9780511543340.
  * [10] A. E. Brouwer, A. M. Cohen, and A. Neumaier, “Theory of Distance-Regular Graphs,” Distance-Regular Graphs, pp. 126–166, 1989, doi: 10.1007/978-3-642-74341-2_4.
  * [11] Athanasiadis, C.A. Some combinatorial properties of flag simplicial pseudomanifolds and spheres. Ark Mat 49, 17–29 (2011). https://doi.org/10.1007/s11512-009-0106-4
  * [12] Bibby, Christin & Odesky, Andrew & Wang, Mengmeng & Wang, Shuyang & Zhang, Ziyi & Zheng, Hailun. (2020). Minimal flag triangulations of lower-dimensional manifolds. Involve, a Journal of Mathematics. 13. 683-703. 10.2140/involve.2020.13.683.
  * [13] de Silva V, Ghrist R. Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology. The International Journal of Robotics Research. 2006;25(12):1205-1222. doi:10.1177/0278364906072252
  * [14] Arai, Zin & Hayashi, Kazunori & Hiraoka, Yasuaki. (2011). Mayer–Vietoris sequences and coverage problems in sensor networks. Japan Journal of Industrial and Applied Mathematics. 28. 237-250. 10.1007/s13160-011-0039-8.
  * [15] Tahbaz-Salehi, Alireza & Jadbabaie, Ali. (2010). Distributed Coverage Verification in Sensor Networks Without Location Information. Automatic Control, IEEE Transactions on. 55. 1837 - 1849. 10.1109/TAC.2010.2047541.
  * [16] Upadhyay, Aakriti & Goldfarb, Boris & Wang, Weifu & Ekenna, Chinwe. (2022). A New Application of Discrete Morse Theory to Optimizing Safe Motion Planning Paths. 10.1007/978-3-031-21090-7_2.
  * [17] Dirafzoon, Alireza & Betthauser, Joseph & Schornick, Jeff & Benavides, Daniel & Lobaton, Edgar. (2014). Mapping of unknown environments using minimal sensing from a stochastic swarm. IEEE International Conference on Intelligent Robots and Systems. 3842-3849. 10.1109/IROS.2014.6943102.
  * [18] Dirafzoon, Alireza & Bozkurt, Alper & Lobaton, Edgar. (2016). A framework for mapping with biobotic insect networks: From local to global maps. Robotics and Autonomous Systems. 88. 10.1016/j.robot.2016.11.004.
  * [19] Hausmann, Jean-Claude. “On the Vietoris-Rips complexes and a Cohomology Theory for metric spaces.” (1996).
  * [20] Latschev, J.. (2001). Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold. Archiv der Mathematik. 77. 522-528. 10.1007/PL00000526.
  * [21] Wachs, Michelle L.. “obstructions to Shellability.” Discrete & Computational Geometry 22 (1997): 95-103.
  * [22] Woodroofe, Russ. “Vertex decomposable graphs and obstructions to shellability.” Proceedings of the American Mathematical Society 137 (2008): 3235-3235.
  * [23] Adams, Henry and Baris Coskunuzer. “Geometric Approaches on Persistent Homology.” SIAM J. Appl. Algebra Geom. 6 (2021): 685-710.