Logspace reduction of directed reachability for bounded genus graphs to the planar case

Abstract

We show that reachability in directed graphs embedded on a fixed surface of arbitrary genus is logspace-reducible to reachability in directed graphs embedded in the plane.

Keywords

• Directed graph reachability
• log-space reduction
• graphs on surfaces