Abstract
In this paper we consider cellular automata where the graph defined by the neighbourhood relations between the cells is a tree “with additional edges”. This includes hyperbolic CA defined by regular tessellations of the two-dimensional hyperbolic plane. It is shown that all X-tree CA and all hyperbolic CA can C-simulate each other with constant slowdown, independent of the “branching factors” of the underlying trees.