This chapter surveys computational topology results in the special, low-dimensional case
where the ambient space is a surface. Surface topology is very well-understood and …

Given a triangulated planar graph G on n vertices and an integer r< n, an r--division of G with
few holes is a decomposition of G into O (n/r) regions of size at most r such that each region …

We study vertex sparsification for distances, in the setting of planar graphs with distortion:
Given a planar graph G (with edge weights) and a subset of k terminal vertices, the goal is to …

For an undirected $ n $-vertex graph $ G $ with non-negative edge-weights, we consider the
following type of query: given two vertices $ s $ and $ t $ in $ G $, what is the weight of a …

Let G be an edge-weighted directed graph with n vertices embedded on an orientable
surface of genus g. We describe a simple deterministic lexicographic perturbation scheme …

We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be
solved in time [Klein, Marx, ICALP 2012] and not in time under the Exponential Time …

Let G be a graph embedded on a surface of genus g with b boundary cycles. We describe
algorithms to compute multiple types of non-trivial cycles in G, using different techniques …

We consider the problem of the minimum genus of a graph, a fundamental measure of non-
planarity. We propose the first formulations of this problem as an integer linear program (ILP) …

Given an undirected, edge-weighted graph G together with pairs of vertices, called pairs of
terminals, the minimum multicut problem asks for a minimum-weight set of edges such that …

How much cutting is needed to simplify the topology of a surface? We provide bounds for
several instances of this question, for the minimum length of topologically non-trivial closed …