Multiple-Source Shortest Paths in Embedded Graphs

Sergio Cabello, Erin Wolf Chambers, Jeff Erickson

Let G be a directed graph with n vertices and non-negative weights in its directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. We describe a rando…