A Jordan Curve Theorem for 2-dimensional Tilings

Let $\mathcal{T}$ be a tiling, $q:\mathbb{R}^{2}\rightarrow\mathcal{D}_{\mathcal{T}}$ the quotient map associated to $\mathcal{D}_{\mathcal{T}}$ and $x\in\mathcal{D}_{\mathcal{T}}$ an arbitrary element.

If $x\in\mathcal{V}_{\mathcal{T}}$ and $U$ is an open neighborhoof of $x$, then $q^{-1}(U)$ is an open, saturated neighborhood of $q^{-1}(x)$. Since $x$ is a vertex, it is contained in the closure of its edges and faces, therefore $q^{-1}(U)$ intersects each element of $\mathcal{E}_{x}\cup\mathcal{F}_{x}$. Moreover, since $q^{-1}(U)$ is a saturated neighborhood then $q^{-1}(U)$ contains all of the faces and edges of $x$, that is, $q^{-1}\left(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x}\right)\subset q^{-1}(U)$. Next we see that $q^{-1}\left(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x}\right)$ is an open set. Let $y\in q^{-1}\left(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x}\right)$. If $y$ is an element of a face of $x$, then that face is an open set contained in $q^{-1}\left(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x}\right)$. If $y$ is an element of an edge $E\in\mathcal{E}_{x}$, then there are two tiles $S,T\in\mathcal{T}$ that have $x$ as a common vertex and such that $y\in E\subset S\cap T$. Furthermore, for any other tile $R\in\mathcal{T}\setminus\{S,T\}$, the point $y$ does not belong to $R$. Since $\mathcal{T}\setminus\{T,S\}$ is a locally finite collection of closed sets, its union is a closed subset of $\mathbb{R}^{2}$ ([5, Theorem 1.1.11.]), thus

is an open neighborhood of $y$ contained in $q^{-1}(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x})$. Finally, if $y=q^{-1}(x)$ we consider the set $\mathcal{S}$ of tiles that contain $y$, and we recall that $\mathcal{S}$ is a finite set. By the previous argument $\mathbb{R}^{2}\setminus\left(\bigcup_{T\in(\mathcal{T}\setminus\mathcal{S})}T\right)$ is an open neighborhood of $y$ that is contained in $q^{-1}\left(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x}\right)$. This proves that $q^{-1}\left(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x}\right)$ is an open set such that

Since $U$ was an arbitrary open neighborhood of $x$ in $\mathcal{D}_{\mathcal{T}}$ we conclude that $\left(\{x\}\cup\mathcal{E}_{x}\cup\mathcal{F}_{x}\right)$ is the smallest neighborhood of $x$ in $\mathcal{D}_{\mathcal{T}}$.

If $x\in\mathcal{E}_{\mathcal{T}}$ and $U$ is an open neighborhood of $x$, then $q^{-1}(U)$ is an open, saturated neighborhood of $q^{-1}(x)$. Since $x$ is an edge we know that it is contained in the closure of its faces, so $q^{-1}(U)$ intersects the two elements of $\mathcal{F}_{x}=\{F_{1},F_{2}\}$. Moreover, since $q^{-1}(U)$ is a saturated neighborhood then $q^{-1}(U)$ contains $F_{1}\cup F_{2}$. Thus, $q^{-1}\left(\{x\}\cup\mathcal{F}_{x}\right)\subset q^{-1}(U)$. In the same vein as the previous case, we can see that $q^{-1}\left(\{x\}\cup\mathcal{F}_{x}\right)$ is open in $\mathbb{R}^{2}$. Since $U$ is an arbitrary open neighborhood of $x$ in $\mathcal{D}_{\mathcal{T}}$, we have that $\left(\{x\}\cup\mathcal{F}_{x}\right)$ is the smallest neighborhood of $x$ in $\mathcal{D}_{\mathcal{T}}$.

In order to complete the proof, we see that if $x\in\mathcal{F}_{\mathcal{T}}$, then $\{x\}$ is open in $\mathcal{D}_{\mathcal{T}}$ since $x$ is the interior of a tile in $\mathbb{R}^{2}$. ∎

Let $H=(V_{H},E_{H})$ be the connectedness graph of $\mathcal{V}_{\mathcal{T}}\cup\mathcal{E}_{\mathcal{T}}$. The set of vertices of $H$ is precisely the set $V_{H}=\mathcal{V}_{\mathcal{T}}\cup\mathcal{E}_{\mathcal{T}}$. We know that the edges of $H$ always denote the adjacency between an edge of the tiling and its two vertices. Therefore, every edge in $E_{H}$ is a pair of the form $\{A,z\}$, where $A\in\mathcal{E}_{z}\subset\mathcal{E}_{\mathcal{T}}$ and $z\in\mathcal{V}_{A}\subset\mathcal{V}_{\mathcal{T}}$. For every $A\in\mathcal{E}_{\mathcal{T}}$, pick a point $x_{A}\in A\subset\mathbb{R}^{2}$. If $x\in\mathcal{V}_{\mathcal{T}}$ is a vertex of $A\in\mathcal{E}_{\mathcal{T}}$, we define $I_{x_{A},x}$ as the connected component of $A\setminus\{x_{A}\}$ delimited by $x_{A}$ and $x$. It is clear that $\{x_{A},x\}\cap I_{x_{A},x}=\emptyset$. Since $A$ is an edge of the tiling, then $I_{x_{A},x}$ is homeomorphic to the interval $(0,1)$ and

Moreover, if $\{x_{A},x\}\neq\{x_{B},y\}$ then $I_{x_{A},x}\cap I_{x_{B},y}=\emptyset$, considering that any two different edges of the tiling have an empty intersection. Therefore the function $\psi:V_{H}\cup E_{H}\rightarrow\mathscr{P}(\mathbb{R}^{2})$ given by

proves the planarity of $H$. ∎

Let $G=(V_{G},E_{G})$ be the connectedness graph of $\mathcal{D}_{\mathcal{T}}$ and $H=(V_{H},E_{H})$ the connectedness graph of $\mathcal{V}_{\mathcal{T}}\cup\mathcal{E}_{\mathcal{T}}$. Then $H$ is a subgraph of $G$ and by Lemma 3.4 there is a bijection $\psi:V_{H}\cup E_{H}\rightarrow|H|\subset\mathscr{P}(\mathbb{R}^{2})$ from the set of vertices and edges of $H$ to a planar embedding $|H|$ of $H$. In order to prove the planarity of $G$, we want to extend the definition of $\psi$ to a function $\phi:V_{G}\cup E_{G}\rightarrow\mathbb{R}^{2}$ satisfying conditions (1)-(4) of Definition 3.3. For that purpose, it suffices to define $\phi$ for every element of $\mathcal{F}_{\mathcal{T}}$ and for every edge of $G$ connecting a face of the tiling with one of its vertices or edges.

Let $C\in\mathcal{F}_{\mathcal{T}}$, we know that there is a unique tile $T$ that has $C$ as a face, and we know that $\mathscr{A}(C)=\mathcal{V}_{C}\cup\mathcal{E}_{C}$. Let $\gamma:\mathbb{B}^{2}\rightarrow T$ be a homeomorphism between $\mathbb{B}^{2}$, the unit closed disk of $\mathbb{R}^{2}$, and $T$. Consider the set $\gamma^{-1}(\mathcal{V}_{C})=\{w_{1},w_{2},\dots,w_{n}\}$, which is contained in $\mathbb{S}^{1}$ since $\gamma$ is a homeomorphism and $\mathcal{V}_{C}\subset\partial T$. Without lost of generality we can suppose that $w_{1},\dots,w_{n}$ are numbered clockwise. Then we can number the set $\gamma^{-1}(\mathcal{E}_{C})=\{B_{1},\dots,B_{n}\}$ denoting by $B_{1}$ the arc delimited by $w_{1}$ and $w_{2}$ and then proceeding in a clockwise manner. For every $i\in\{1,\dots,n\}$, define $A_{i}:=\gamma(B_{i})$, considering that $\gamma$ is a homeomorphism we can assure that $\mathcal{E}_{C}=\{A_{1},\dots,A_{n}\}$. Being consistent with the notation introduced in Lemma 3.4, we have a point $x_{A_{i}}\in A_{i}$ such that $\psi(A_{i})=\{x_{A_{i}}\}$. Let $b_{i}:=\gamma^{-1}(x_{A_{i}})$, which is an element of $B_{i}\subset\mathbb{S}^{1}\setminus(\gamma^{-1}(\mathcal{V}_{C}))$.

For every $w\in\{w_{1},\dots,w_{n},b_{1},\dots,b_{n}\}$, let $L_{w}:=\left\{tw\leavevmode\nobreak\ |\leavevmode\nobreak\ t\in(0,1)\right\}.$ Now we consider the family

whose elements are pairwise disjoint and they are contained in $\operatorname{Int}{\mathbb{B}^{2}}$.

Let $x_{C}:=\gamma(0,0)$. Since $(0,0)\in\operatorname{Int}{\mathbb{B}^{2}}$, it follows that $x_{C}\in C$. Each element of the family $\gamma(\mathcal{L}_{C})=\{\gamma(L)\leavevmode\nobreak\ |\leavevmode\nobreak\ L\in\mathcal{L}_{C}\}$ is an arc delimited by $x_{C}$ and one of the points in the set $\{v_{1},\dots,v_{n},x_{A_{1}},\dots,x_{A_{n}}\}$, where $v_{i}=\gamma(w_{i})\in\mathcal{V}_{C}$. Thus we can denote each arc $\gamma(L)\in\gamma(\mathcal{L}_{C})$ as $M_{x_{C},v}$, where $v$ is the point in $\{v_{1},\dots,v_{n},x_{A_{1}},\dots,x_{A_{n}}\}$ that, alongside $x_{C}$, delimits $\gamma(L)$. From its definition, it is clear that $M_{x_{C},v}\cap\{x_{C},v\}=\emptyset$. These arcs are pairwise disjoint, since $\gamma$ is a homeomorphism and the elements of $\mathcal{L}_{C}$ are pairwise disjoint. Also, each arc $M_{x_{C},v}$ is contained in $C$, since the elements of $\mathcal{L}_{C}$ are contained in $\operatorname{Int}{\mathbb{B}^{2}}$. From here we can infer that if $D$ is another face of the tiling, then the elements of $\gamma(\mathcal{L}_{C})$ and $\gamma(\mathcal{L}_{D})$ are pairwise disjoint. Furthermore, we can also conclude that the elements of $\gamma(\mathcal{L}_{C})$ do not intersect $\partial T$. Lastly, note that $M_{x_{C},v}\in\gamma(\mathcal{L}_{C})$ implies

Therefore the function $\phi:V_{G}\cup E_{G}\rightarrow\mathscr{P}(\mathbb{R}^{2})$ given by

proves the planarity of $G$. ∎

Let $G$ be the connectedness graph of $\mathcal{D}_{\mathcal{T}}$, it suffices to see that $G$ satisfies the hypotheses of Theorem 4.3. Let $q:\mathbb{R}^{2}\rightarrow\mathcal{D}_{\mathcal{T}}$ be the quotient function associated to the topology of $\mathcal{D}_{\mathcal{T}}$ (see equation 3.1). We know that $q$ is continuous and therefore the connectedness of $\mathcal{D}_{T}$ is guaranteed by the connectedness of $\mathbb{R}^{2}$. Moreover, we know that $\mathcal{D}_{T}$ is an Alexandrov discrete space, so by Theorem 2.5 we have that $G$ is connected. In addition, $G$ is a planar graph by Proposition 3.5.

It only rests us to prove that $G$ is a locally Hamiltonian graph. By Theorem 3.2, if $x$ is a vertex of $G$ we have that:

If $x\in\mathcal{V}_{\mathcal{T}}$, we know that at least three tiles intersect in $x$. Each of these tiles has exactly two edges whose vertex is $x$. This fact allows us to infer that if we consider the set $\mathcal{E}_{x}$ (which is finite) and we number their elements clockwise, then every two consecutive edges determine a face of $x$ (and none of these faces is determined by two different pairs of edges). We also know that every edge of $x$ is determined by exactly two faces of $x$. Lastly, we know that in the connectedness graph there are no two adjacent edges nor two adjacent faces. Thus the subgraph induced by $\mathcal{E}_{x}\cup\mathcal{F}_{x}$ is a cycle wherein the vertices of the graph corresponding to edges of the tiling and the vertices of the graph corresponding to faces of the tiling alternate.

If $x\in\mathcal{E}_{\mathcal{T}}$, $x$ has exactly two vertices and two faces, furthermore, both vertices are vertices of both faces. For that reason the subgraph of $G$ induced by $\mathcal{V}_{x}\cup\mathcal{F}_{x}$ is a cycle with exactly four vertices.

Finally, if $x\in\mathcal{F}_{\mathcal{T}}$ we recall the analysis made in Proposition 3.5 to conclude that the vertices and edges of $x$ alternate in $\partial x$, allowing us to verify that $\mathcal{V}_{x}\cup\mathcal{E}_{x}$ is a cycle.

In any case, we have proved that the subgraph induced by $\mathscr{A}(x,G)$ is a cycle and thus $G$ is locally Hamiltonian. In addition, we know that since $J$ is a digital Jordan curve, then the subgraph induced by $J$ in $G$ is a graph-theoretical Jordan curve. Hence, by Theorem 4.3 we can conclude that $G\setminus J$ has exactly two connected components in $G$.

To finish the proof, recall that $\mathcal{D}_{\mathcal{T}}$ is an Alexandrov space. Since $G\setminus J$ has exactly two connected components in $G$, by Theorem 2.5 we have that $\mathcal{D}_{\mathcal{T}}\setminus J$ has exactly two connected components. Moreover, we know that the connected components of $\mathcal{D}_{\mathcal{T}}\setminus J$ are precisely the vertices of the connected components of $G\setminus J$; in other words, the connected components of $\mathcal{D}_{\mathcal{T}}\setminus J$ are its interior $I(J)$, which is bounded, and its exterior $O(J)$, which is not. ∎

Let $x\in J$ and let $G$ be the connectedness graph of $\mathcal{D}_{\mathcal{T}}$. We proceed by contradiction. Suppose that $\mathscr{A}(x)\cap I(J)=\emptyset$ and let $x_{0}$ and $x_{1}$ be the two adjacent points to $x$ in $J$. It is clear that $x_{0}$ and $x_{1}$ are not adjacent. We know that the subgraph induced by $\mathscr{A}(x)$ is a cycle with at least four elements. For that reason there are two paths contained in $\mathscr{A}(x,G)$ that only intersect at $x_{0}$ and $x_{1}$. Let $a$ and $b$ be two vertices, different from $x_{0}$ and $x_{1}$, in each of these paths. Since $\mathscr{A}(x)\cap I(J)=\emptyset$, then, with the exception of $x_{0}$ and $x_{1}$, the vertices of the paths we mentioned earlier are contained in $O(J)$. In particular, $a,b\in O(J)$.

Since $\mathcal{T}$ is a tiling, $G$ is a planar graph and thus there is a map $\psi:V_{G}\cup E_{G}\to\mathscr{P}(\mathbb{R}^{2})$ that attests the planarity of $G$. Let $H$ be the subgraph induced by the vertices $V_{H}:=I(J)\cup J$ in $G$. Being a subgraph of $G$, $H$ is a planar graph too. Since $\mathscr{A}(x)\cap I(J)=\emptyset$, we have that $\mathscr{A}(x)\cap(I(J)\cup J)=\{x_{0},x_{1}\}$, therefore $x$ is a vertex of exactly two faces of $H$. Let $\mathrm{C}$ be the cycle that determines the bounded face of $H$ having $x$ as a vertex (the other face contains the exterior face of the subgraph induced by the vertices of $J$). Then we know that $\bigcup\psi(\mathrm{C})$ is the boundary of a set $\mathrm{D}$, homeomorphic to a closed disk, and that $\psi(x_{0}),\psi(x),\psi(x_{1})\subset\bigcup\psi(\mathrm{C})=\partial\mathrm{D}$.

Now we construct a graph $\Gamma$ with the set of vertices $V_{\Gamma}=V_{G}\cup\{p\}$, where $p\notin V_{G}$, and the set of edges $E_{\Gamma}=E_{G}\cup\left\{\{p,w\}\leavevmode\nobreak\ |\leavevmode\nobreak\ w\in V_{\mathrm{C}}\right\}$. We sustain that $\Gamma$ is a planar graph. Indeed, since $\mathrm{D}$ is homeomorphic to a closed disk and $\psi(x_{0}),\psi(x),\psi(x_{1})\subset\partial\mathrm{D}$, we can replicate the construction of the point $x_{C}$ and the sets $M_{x_{C},v}$ in the proof of Proposition 3.5 to prove the existence of a point $x_{p}\in\operatorname{Int}\mathrm{D}$ and sets $M_{x_{p},w}\subset\operatorname{Int}\mathrm{D}$ such that the function $\phi:V_{\Gamma}\cup E_{\Gamma}\rightarrow\mathscr{P}(\mathbb{R}^{2})$ defined as

proves the planarity of $\Gamma$.

However, if we take a look at the sets of vertices $\{p,a,b\}$ and $\{x_{0},x,x_{1}\}$, we see that $\Gamma$ contains a subdivision of a complete bipartite graph $K_{3,3}$, which contradicts Kuratowski’s theorem ([3, Theorem 4.4.6]). Therefore we have proved that $\mathscr{A}(x)\cap I(J)\neq\emptyset$. ∎

a)$\implies$b). $I(J)\cup O(J)$ is the complement of $J$ and thus it is open. In addition, since $\mathcal{D}_{\mathcal{T}}$ is an Alexandrov space, Theorem 2.5 guarantees that $I(J)$ and $O(J)$ are open and closed in $I(J)\cup O(J)$, because they are the connected components of $I(J)\cup O(J)$. Since the latter is open in $\mathcal{D}_{\mathcal{T}}$, we conclude that $I(J)$ and $O(J)$ are also open in $\mathcal{D}_{\mathcal{T}}.$

b)$\implies$c). We prove the contrapositive. Suppose there is an element $x\in\operatorname{Int}{\left(\overline{J}\right)}$. This implies that $N(x)\subset\overline{J}$. In particular, we have that $x\in\overline{J}$ and hence $\overline{\{x\}}\subset\overline{J}$. Thus $\mathscr{A}(x)\cup\{x\}\subset\overline{J}$. In this situation, $\overline{J}$ can not be a digital Jordan curve since the connectedness graph of $\mathscr{A}(x)\cup\{x\}$ contains at least one vertex, one edge and one face adjacent to each other; in other words, the connectedness graph of $\mathscr{A}(x)\cup\{x\}$ contains cycles of length $3$. For that reason, $J$ is not closed and therefore $I(J)\cup O(J)$ is not open, which in turn implies that b) is false.

c)$\implies$d). Suppose that $I(J)\cup O(J)$ is not dense. Since $\mathcal{D}_{\mathcal{T}}$ is the disjoint union of $I(J)$, $O(J)$ and $J$, there is a point $x\in J$ such that $N(x)\cap\left(I(J)\cup O(J)\right)=\emptyset$. Therefore $N(x)\subset J$, so $x\in\operatorname{Int}(J)$ and thus $\operatorname{Int}{\left(\overline{J}\right)}\neq\emptyset$.

d)$\implies$e). Assume there is a point $x\in J\cap\mathcal{F}_{\mathcal{T}}$. Thus $N(x)=\{x\}\subset J$. Since $J\cap\left(I(J)\cup O(J)\right)=\emptyset$, we have that $N(x)\cap\left(I(J)\cup O(J)\right)=\emptyset$ and therefore $I(J)\cup O(J)$ cannot be dense.

e)$\implies$f). First let us prove that $J$ is closed. By e), the elements of $J$ are alternating vertices and edges. The closure of a vertex is the vertex itself, and the closure of an edge is the union of the edge and its two vertices. Since the vertices and edges alternate in $J$, the vertices of each edge in $J$ are contained in $J$. Therefore the closure of each element of $J$ is contained in $J$. Since $\mathcal{D}_{\mathcal{T}}$ is an Alexandrov discrete space this implies that $J$ is closed.

Now by the implication a)$\implies$b), we infer that $I(J)$ and $O(J)$ are open. This proves that $\partial(I(J))=\overline{(I(J))}\setminus I(J)$. Furthermore, since $\mathcal{D}_{\mathcal{T}}$ is the disjoint union of $J$, $I(J)$ and $O(J)$, we conclude that $I(J)\cup J$ is a closed set that contains $I(J)$. Thus