<p>I would like to know if the following problem is known and has been studied:</p>
<p>Consider an infinite directed graph that can be built on the infinite lattice <strong>&quot;tiling&quot;</strong> a finite set of subgraphs, more formally:</p>
<ul>
<li>the set of vertices <span class="math-container">$V$</span> is a subset of the infinite lattice (<span class="math-container">$V \subseteq \{ (x,y) \mid x,y \in \mathbb{N} \}$</span>), and</li>
<li>the set of edges <span class="math-container">$E = \bigcup E_i$</span> (which also defines <span class="math-container">$V$</span>) is given using a finite set of linear equations:</li>
</ul>
<p><span class="math-container">$E_i = \{ (P_i,P_i') \}$</span> where the two nodes <span class="math-container">$P_i,P'_i$</span> are nodes at coordinates:<br>
<span class="math-container">$P_i = (x_{i} + a_ix, y_{i} + b_i y)$</span>,<br>
<span class="math-container">$P_i' = (x'_{i} + c_i x, y'_{i} + d_i y)$</span></p>
<p>For each <span class="math-container">$E_i$</span> we can have <em>one</em> the following cases: <span class="math-container">$x,y\geq 0$</span> (which creates an infinite rectangle of &quot;tiles&quot;); <span class="math-container">$x \geq 0, y = 0$</span> (which creates an infinite horizontal strip of &quot;tiles&quot;), <span class="math-container">$x = 0, y \geq 0$</span> (which creates an infinite vertical strip of &quot;tiles&quot;); <span class="math-container">$x=y$</span> (which creates an infinite diagonal strip of &quot;tiles&quot;).</p>
<p>So the set <span class="math-container">$E_i$</span> is defined by the constants <span class="math-container">$x_i, x'_i, y_i, y'_i, a_i, b_i, c_i, d_i$</span> and there is an edge for every value taken by <span class="math-container">$x,y$</span>.</p>
<p>The set of nodes is given by the union of all the endpoints of the edges.</p>
<p><img src="https://i.sstatic.net/6gavS.png" alt="enter image description here" /></p>
<p>It's not so hard to prove that the s-t connectivity problem (&quot;Given two nodes <span class="math-container">$s,t$</span>; is there a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>?&quot;) is <em>undecidable for non planar graphs</em> (using for example a set of &quot;graph tiles&quot; arranged to simulate the configurations of a two counters machine, in which the value of the counter <span class="math-container">$c_1$</span> is the <span class="math-container">$x$</span>-coordinate, and the value of the counter <span class="math-container">$c_2$</span> is the <span class="math-container">$y$</span>-coordinate).</p>
<blockquote>
<p>But, is it still undecidable if the graph is planar ?</p>
<p>If it is still undecidable on planar graphs, for which subclasses of graphs the problem becomes decidable ?</p>
</blockquote>

CC BY-SA 3.0
2015-03-30T19:53:07.247Z
Im having trouble understanding the question: In the set of equations defining the graph, should the $c$ be $c_i$? Further, is the edge set $E_i$ defined by the constants $\{x_i, y_i, x_i', y_i', a_i, b_i, c_i, d_i\}$ and there is an edge for every $x,y \in \mathbb{N}$? Has undecidability been proved for the graphs you are describing and you are asking what happens if the input graph is planar (the natural embedding is plane?) or do you mean something else. Sorry for all the confusion...
daniello
CC BY-SA 3.0
2015-03-30T19:59:51.773Z
If you are allowed $x,y \in \mathbb{N}$, then I don't see how your example works. $(x_i + a_ix, y_i + b_i y)$ can give a two-dimensional rectangular array of points, or a one-dimensional array of points either horizontally or vertically, but your picture has one-dimensional diagonal arrays.
Peter Shor 
CC BY-SA 3.0
2015-03-30T20:46:52.660Z
@Peter: Probably he has meant x=y.
domotorp
CC BY-SA 3.0
2015-03-30T22:29:54.173Z
@PeterShor: my example is not so clear, I'll try to improve the question. However, a two dimensional (infinite) rectangular array of "tiles" (repeated for arbitrary $x,y$), one horizontal array of tiles (repeated for $x \geq 0, y=0$) and one vertical array of tiles (repeated for $x=0, y \geq 0$) are enough to give undecidability for the non-planar case.
Marzio De Biasi
CC BY-SA 3.0
2015-03-30T22:34:19.640Z
@daniello: yes $c$ is $c_i$, I'll fix it. The undecidability result for the non-planar case has came to my mind while thinking about a generalization of a game, but I think it has no deep insights. I tried to search what happens adding the planarity constraint but I didn't find too many papers, even for infinite graphs not built according to my rules.
Marzio De Biasi
CC BY-SA 3.0
2015-03-30T22:53:03.703Z
@domotorp: not necessarily, for undecidability in the non-planar case we need $(x\geq0,y\geq0)$, $(x\geq0,y=0)$, $(x=0,y\geq0)$. See if the question is more clear (and correct) after the reformulation; the informal idea is very "basic": an infinite graph that can be built tiling an infinite number of "subgraph tiles" from a finite set (arranging them in infinite rectangles, or infinite horizontal/vertical strips).
Marzio De Biasi
<reference-request><planar-graphs><undecidability>
s-t connectivity on infinite planar graphs with finite description
Marzio De Biasi
# s-t connectivity on infinite planar graphs with finite description

(Asked by: username_0 on 2015-03-30)

I would like to know if the following problem is known and has been studied:

Consider an infinite directed graph that can be built on the infinite lattice **"tiling"** a finite set of subgraphs, more formally:

* the set of vertices $V$ is a subset of the infinite lattice ($V \subseteq \{ (x,y) \mid x,y \in \mathbb{N} \}$), and
* the set of edges $E = \bigcup E\_i$ (which also defines $V$) is given using a finite set of linear equations:

$E\_i = \{ (P\_i,P\_i') \}$ where the two nodes $P\_i,P'\_i$ are nodes at coordinates:  
$P\_i = (x\_{i} + a\_ix, y\_{i} + b\_i y)$,  
$P\_i' = (x'\_{i} + c\_i x, y'\_{i} + d\_i y)$

For each $E\_i$ we can have *one* the following cases: $x,y\geq 0$ (which creates an infinite rectangle of "tiles"); $x \geq 0, y = 0$ (which creates an infinite horizontal strip of "tiles"), $x = 0, y \geq 0$ (which creates an infinite vertical strip of "tiles"); $x=y$ (which creates an infinite diagonal strip of "tiles").

So the set $E\_i$ is defined by the constants $x\_i, x'\_i, y\_i, y'\_i, a\_i, b\_i, c\_i, d\_i$ and there is an edge for every value taken by $x,y$.

The set of nodes is given by the union of all the endpoints of the edges.

![enter image description here](https://i.sstatic.net/6gavS.png)

It's not so hard to prove that the s-t connectivity problem ("Given two nodes $s,t$; is there a path from $s$ to $t$?") is *undecidable for non planar graphs* (using for example a set of "graph tiles" arranged to simulate the configurations of a two counters machine, in which the value of the counter $c\_1$ is the $x$-coordinate, and the value of the counter $c\_2$ is the $y$-coordinate).

> But, is it still undecidable if the graph is planar ?
>
> If it is still undecidable on planar graphs, for which subclasses of graphs the problem becomes decidable ?

**Tags:** reference-request, planar-graphs, undecidability

> **Comments:**
> **username_1**: Im having trouble understanding the question: In the set of equations defining the graph, should the $c$ be $c_i$? Further, is the edge set $E_i$ defined by the constants $\{x_i, y_i, x_i', y_i', a_i, b_i, c_i, d_i\}$ and there is an edge for every $x,y \in \mathbb{N}$? Has undecidability been proved for the graphs you are describing and you are asking what happens if the input graph is planar (the natural embedding is plane?) or do you mean something else. Sorry for all the confusion...  
> **username_2**: If you are allowed $x,y \in \mathbb{N}$, then I don't see how your example works. $(x_i + a_ix, y_i + b_i y)$ can give a two-dimensional rectangular array of points, or a one-dimensional array of points either horizontally or vertically, but your picture has one-dimensional diagonal arrays.  
> **username_3**: @Peter: Probably he has meant x=y.  
> **username_0**: @PeterShor: my example is not so clear, I'll try to improve the question. However, a two dimensional (infinite) rectangular array of "tiles" (repeated for arbitrary $x,y$), one horizontal array of tiles (repeated for $x \geq 0, y=0$) and one vertical array of tiles (repeated for $x=0, y \geq 0$) are enough to give undecidability for the non-planar case.  
> **username_0**: @username_1: yes $c$ is $c_i$, I'll fix it. The undecidability result for the non-planar case has came to my mind while thinking about a generalization of a game, but I think it has no deep insights. I tried to search what happens adding the planarity constraint but I didn't find too many papers, even for infinite graphs not built according to my rules.  
> **username_0**: @username_3: not necessarily, for undecidability in the non-planar case we need $(x\geq0,y\geq0)$, $(x\geq0,y=0)$, $(x=0,y\geq0)$. See if the question is more clear (and correct) after the reformulation; the informal idea is very "basic": an infinite graph that can be built tiling an infinite number of "subgraph tiles" from a finite set (arranging them in infinite rectangles, or infinite horizontal/vertical strips).  

---

## 0 answers

