We study a general family of facility location problems defined on planar graphs and on the
2-dimensional plane. In these problems, a subset of k objects has to be selected, satisfying …

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 …

For p∈ N, a coloring λ of the vertices of a graph G is p-centered if for every connected
subgraph H of G, either H receives more than p colors under λ or there is a color that …

In the PLANAR DISJOINT PATHS problem, one is given an undirected planar graph with a
set of k vertex pairs \left(s_i,t_i\right) and the task is to find k pairwise vertex-disjoint paths …

Abstract In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of n
points in ℝ2 called terminals and a parameter k, and the goal is to compute a Steiner tree …

There are numerous examples of the so-called" square root phenomenon" in the field of
parameterized algorithms: many of the most fundamental graph problems, parameterized by …

Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks
whether there exists a subset U⊆ V (G) of size at most k that hits all induced cycles of size at …

By now, we have a good understanding of how NP-hard problems become easier on graphs
of bounded treewidth and bounded cliquewidth: for various problems, matching upper …

In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k
vertex pairs,{si, ti} i= 1 k, and the task is to find k pairwise vertex-disjoint paths such that the …

The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph
G and integer k, whether k vertices can be removed from G such that the resulting graph …