A pseudo-random network mobile automaton with linear growth

Based on the mobile automaton computational paradigm, a (fully deterministic) algorithm is introduced that grows planar graphs while exhibiting surprisingly uniform pseudo-random dynamics. The graph growth rate, as a function of the automaton steps, is O(n), and nicely combines with the O(Sqrt[n]) of a previously introduced algorithm of ours: these two rates are also achieved by two most elementary visit-and-grow procedures with regular dynamics, of which our automata can be viewed as randomized versions. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested, but other application areas are envisaged as well.