Abstract: The study of optimal subgraphs, such as minimum spanning trees and shortest paths, has been a staple of computer science for more than fifty years. Similarly, optimal straight-line geometric graphs, such as convex hulls and Voronoi diagrams, have been a standard object of study in computational geometry since its earliest beginnings. These optimal graph structures are critical components of countless graph and geometry algorithms. It is therefore natural to consider algorithms to compute optimal graphs in more general topological spaces. Even though embedded graphs have been a standard tool in topology for more than 100 years, relatively little is known about this class of algorithmic problem. This talk will survey algorithms for computing optimal graphs on topological surfaces, with an emphasis on open problems. For example: How quickly can we compute the shortest nontrivial cycle in a given surface? The shortest cycle in a given homotopy class? The shortest cycle that cuts the surface into two nontrivial components? The shortest graph that cuts the surface into a disk? The shortest pants decomposition? The shortest canonical homotopy basis? Neither efficient algorithms, approximations, or hardness results are known for most of these problems. For the few problems where algorithms are known, there is little reason to believe that are as fast as possible.