There are many Turing complete computation models and new ones are devised all the time.
I am looking for Turing-complete computation models based on graphs?
There are many Turing complete computation models and new ones are devised all the time.
I am looking for Turing-complete computation models based on graphs?
Only an extended comment: I only heard about it (and I know almost nothing about it :), but there is a computational model based on Graph Rewriting
From Wikipedia: "... The basic idea is that the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph. ..."
You can take a look at: D. L. McBurney and M. R. Sleep. 1991. Graph Rewriting as a computational model. In Proceedings of the UK/Japan workshop on Concurrency : theory, language, and architecture: theory, language, and architecture, A. Yonezawa and T. Lto (Eds.). Springer-Verlag New York, Inc., New York, NY, USA, 235-256.
or this thesis for an introduction: König, Barbara (December 2004). Analysis and Verification of Systems with Dynamically Evolving Structure. Habilitation thesis, Universität Stuttgart, pp. 65–180.
But I don't know if it is still an active field of research.
As in my comment, the configuration graph (Chapter 4.1.1. of Arora-Barak) is a simple way to view a Nondeterministic Turing Machine (NTM) as a graph. The vertices of the graph are labeled by configurations: the internal state of the NTM, the contents of the tape, and head positions. There is a directed edge from vertex $c_1$ to vertex $c_2$ if the NTM can move from $c_1$ to $c_2$ in one step.
This is especially useful for arguing about space-bounded computation. If the space used by the NTM is bounded by $s(n)$, then on input size $n$ you only need to consider a configuration graph with $O(2^{s(n)})$ vertices. Then a lot of complexity results follow from algorithms for directed $s$-$t$ connectivity: Savitch's theorem (NPSPACE = PSPACE) follows from an algorithm that uses $O(\log^2 |V|)$ space, PSPACE in EXP (or, scaling down, L in P) follows from DFS, etc. Similarly, you can show that directed connectivity is complete for NL under L reductions, so NL is equal to L if and only if there is a logspace algorithm for directed $s$-$t$ connectivity.
You can perform universal computation using zero forcing: a simple, repeated transformation of (improper) 2-colourings of vertices. Starting from an initial configuration in which most vertices are coloured white, except for some black "input" vertices, you repeatedly change the colour of any vertex with exactly one white neighbour to black. Logic gates are represented by specific gadgets which are subgraphs.
D. Burgarth, V. Giovannetti, L. Hogben, S. Severini, M. Young.
Logic circuits from zero forcing.
[arXiv:1106.4403]
Following vzn's comment, you can define a straightforward extension of TMs using graph products. Define a "graph machine" as a tuple $M = (S,T)$ where $S$ is a sets of states, and $T$ is a binary relation over $S \times S$. Fix a graph family $\cal{G}$, and consider the following problem: given a graph $G \in \cal{G}$ and two $S$-labelings $L_1,L_2$ of $G$, does there exist a graph $H \in \cal{G}$ with two distinguished vertices $s,t$ and a $S$-labeling $M$ of $G \times H$ such that:
(i) the restriction of $M$ to $G \times \{s\}$ and $G \times \{t\}$ coincides with $L_1$ and $L_2$ respectively;
(ii) for each "square" of $G \times H$ of the form
(u_1,v_1) - (u_1,v_2) | | (u_2,v_1) - (u_2,v_2)
with $s_i = M(u_1,v_i)$ and $s'_i = M(u_2,v_i)$, it holds that $(s_1,s_2) T (s'_1,s'_2)$.
It shouldn't be difficult to show that this problem is Turing-complete when $\cal{G}$ is the class of paths, intuitively you can encode the computation by a grid with "local" rules applied to each square.