This enabled them to prove that DTIME(f(n)) is contained in DSPACE(f(n)/log f(n)) for all time-constructible f. Lipton and Tarjan [2] showed that any n-vertex planar acyclic directed graph with maximum in-degree k can be pebbled using O(√n + k log2 n) pebbles.
Alon, Seymour and Thomas [3] showed that any n-vertex acyclic directed graph with no kh-minor and with maximum in-degree k can be pebbled using O(h3/2 n1/2 + k log n) pebbles.
An extension of this game, known as "black-white pebbling", was developed by Stephen Cook and Ravi Sethi in a 1976 paper.
They determined the computational complexity of the one-player and two-player versions of this game, and special cases thereof.
In the two-player version, the players take turns moving pebbles.