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

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 ?

  • 1
    $\begingroup$ 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... $\endgroup$ – daniello Mar 30 '15 at 19:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Shor Mar 30 '15 at 19:59
  • $\begingroup$ @Peter: Probably he has meant x=y. $\endgroup$ – domotorp Mar 30 '15 at 20:46
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Mar 30 '15 at 22:29
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Mar 30 '15 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.