Reachability in O ( log n ) Genus Graphs is in Unambiguous

摘要

Given the polygonal schema embedding of an O ( logn ) genus graph G and two vertices s and t in G , we show that deciding if there is a path from s to t in G is in unambiguous logarithmic space.