Determining the Genus of a Map by Local Observation of a Simple Random Process

Itai Benjamini, Laszlo Lovasz

Given a graph embedded in an orientable surface, a process consisting of random excitations and random node and face balancing is constructed and analyzed. It is shown that given a…