The complexity of pebbling reachability and solvability in planar and outerplanar graphs ?
Given a simple, connected graph, a pebbling configuration is a function from its vertex set to the nonnegative integers. A pebbling move  between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r r is said to be reachable  from a configuration if there exists a sequence of pebbling moves that places at least one pebble on r r . A configuration is solvable  if every vertex is reachable. We prove that determining reachability of a vertex and solvability of a configuration are NP-complete on planar graphs. We also prove that both reachability and solvability can be determined in O(n6) O ( n 6 ) time on planar graphs with diameter two. Finally, for outerplanar graphs, we present a linear algorithm for determining reachability and a quadratic algorithm for determining solvability. To prove this result, we provide linear algorithms to determine all possible maximal configurations of pebbles that can be placed on the endpoints of a path and on two adjacent vertices in a cycle.
planar outerplanar np-complete graph pebbling