Nöllenburg, M., Wolff, A.: Drawing and Labeling High-Quality Metro Maps by
Mixed-Integer Programming.IEEE Transactions on Visualization and Computer Graphics.17,626--641 (2011).
Metro maps are schematic diagrams of public
transport networks that serve as visual aids for
route planning and navigation tasks. It is a
challenging problem in network visualization to
automatically draw appealing metro maps. There are
two aspects to this problem that depend on each
other: the layout problem of finding station and
link coordinates and the labeling problem of placing
non-overlapping station labels. \par In this paper
we present a new integral approach that solves the
combined layout and labeling problem (each of which,
independently, is known to be NP-hard) using
mixed-integer programming (MIP). We identify seven
design rules used in most real-world metro maps. We
split these rules into hard and soft constraints and
translate them into a MIP model. Our MIP formulation
finds a metro map that satisfies all hard
constraints (if such a drawing exists) and minimizes
a weighted sum of costs that correspond to the soft
constraints. We have implemented the MIP model and
present a case study and the results of an expert
assessment to evaluate the performance of our
approach in comparison to both manually designed
official maps and results of previous layout
methods.
Rutter, I., Wolff, A.: Computing Large Matchings Fast.ACM Transactions on Algorithms.7, (2010).
In this paper we present algorithms for computing
large matchings in 3-regular graphs, graphs with
maximum degree 3, and 3-connected planar graphs.
The algorithms give a guarantee on the size of the
computed matching and take linear or slightly
superlinear time. Thus they are faster than the
best-known algorithm for computing maximum matchings
in general graphs, which runs in $O(nm)$
time, where $n$ denotes the number of vertices
and $m$ the number of edges of the given graph. For
the classes of 3-regular graphs and graphs with
maximum degree 3, the bounds we achieve are known to
be best possible. \par We also investigate graphs
with block trees of bounded degree, where the
$d$-block tree is the adjacency graph of the
$d$-connected components of the given graph. In
3-regular graphs and 3-connected planar graphs with
bounded-degree 2- and 4-block trees, respectively,
we show how to compute maximum matchings in
slightly superlinear time.
Erlebach, T., Hagerup, T., Jansen, K., Minzlaff, M., Wolff, A.: Trimming of Graphs, with Application to Point
Labeling.Theory of Computing Systems.47,613--636 (2010).
For $t>0$ and $g\ge 0$, a vertex-weighted graph of
total weight $W$ is $(t,g)$-trimmable if it
contains a vertex-induced subgraph of total weight
at least $(1-1/t)W$ and with no simple path of more
than $g$ edges. A family of graphs is
trimmable if for every constant $t>0$, there
is a constant $g\ge 0$ such that every
vertex-weighted graph in the family is
$(t,g)$-trimmable. We show that every family of
graphs of bounded domino treewidth is trimmable.
This implies that every family of graphs of bounded
degree is trimmable if the graphs in the family have
bounded treewidth or are planar. We also show that
every family of directed graphs of bounded layer
bandwidth (a less restrictive condition than bounded
directed bandwidth) is trimmable. As an application
of these results, we derive polynomial-time
approximation schemes for various forms of the
problem of labeling a subset of given weighted point
features with nonoverlapping sliding axes-parallel
rectangular labels so as to maximize the total
weight of the labeled features, provided that the
ratios of label heights or the ratios of label
lengths are bounded by a constant. This settles one
of the last major open questions in the theory of
map labeling.
Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C.-S., Spillner, A., Wolff, A.: Untangling a Planar Graph.Discrete Computational Geometry.42,542--569 (2009).
A straight-line drawing $\delta$ of a planar graph
$G$ need not be plane, but can be made so by
untangling it, that is, by moving some of the
vertices of $G$. Let shift$(G,\delta)$ denote the
minimum number of vertices that need to be moved to
untangle $\delta$. We show that shift$(G,\delta)$ is
NP-hard to compute and to approximate. Our hardness
results extend to a version of
1BendPointSetEmbeddability, a well-known
graph-drawing problem. \par Further we define
fix$(G,\delta)=n-shift(G,\delta)$ to be the maximum
number of vertices of a planar $n$-vertex graph $G$
that can be fixed when untangling $\delta$. We give
an algorithm that fixes at least $((łog
n)-1)/łog łog n$ vertices when untangling a
drawing of an $n$-vertex graph $G$. If $G$ is
outerplanar, the same algorithm fixes at least
$n/2$ vertices. On the other hand we
construct, for arbitrarily large $n$, an $n$-vertex
planar graph $G$ and a drawing $\delta_G$ of $G$
with fix$(G,\delta_G) łe n-2+1$ and an
$n$-vertex outerplanar graph $H$ and a drawing
$\delta_H$ of $H$ with fix$(H,\delta_H) łe 2
n-1+1$. Thus our algorithm is asymptotically
worst-case optimal for outerplanar graphs.
Nöllenburg, M., Merrick, D., Wolff, A., Benkert, M.: Morphing Polylines: A Step Towards Continuous
Generalization.Computers, Environment and Urban Systems.32,248--260 (2008).
We study the problem of morphing between two
polylines that represent linear geographical
features like roads or rivers generalized at two
different scales. This problem occurs frequently
during continuous zooming in interactive
maps. Situations in which generalization operators
like typification and simplification replace, for
example, a series of consecutive bends by fewer
bends are not always handled well by traditional
morphing algorithms. We attempt to cope with such
cases by modeling the problem as an optimal
correspondence problem between characteristic parts
of each polyline. A dynamic programming algorithm is
presented that solves the matching problem in
$O(nm)$ time, where $n$ and $m$ are the respective
numbers of characteristic parts of the two
polylines. In a case study we demonstrate that the
algorithm yields good results when being applied to
data from mountain roads, a river and a region
boundary at various scales.
van Kreveld, M., Strijk, T., Wolff, A.: Point Labeling with Sliding Labels.Computational Geometry: Theory and Applications.13,21--47 (1999).
This paper discusses algorithms for labeling sets of
points in the plane, where labels are not restricted
to some finite number of positions. We show that
continuously sliding labels allow more points to be
labeled both in theory and in practice. We define
six different models of labeling. We compare models
by analyzing how many more points can receive labels
under one model than another. We show that
maximizing the number of labeled points is NP-hard
in the most general of the new models. Nevertheless,
we give a polynomial-time approximation scheme and a
simple and efficient factor-1/2 approximation
algorithm for each of the new models. \par Finally,
we give experimental results based on the factor-1/2
approximation algorithm to compare the models in
practice. We also compare this algorithm
experimentally to other algorithms suggested in the
literature.