
Nöllenburg, M., Wolff, A.: Drawing and Labeling HighQuality Metro Maps by MixedInteger Programming. IEEE Transactions on Visualization and Computer Graphics. 17, 626641 (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 nonoverlapping 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 NPhard) using mixedinteger programming (MIP). We identify seven design rules used in most realworld 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.

Erlebach, T., Hagerup, T., Jansen, K., Minzlaff, M., Wolff, A.: Trimming of Graphs, with Application to Point Labeling. Theory of Computing Systems. 47, 613636 (2010).
For \($t>0$\) and \($g\ge 0$\), a vertexweighted graph of total weight \($W$\) is \emph\($(t,g)$\)trimmable if it contains a vertexinduced subgraph of total weight at least \($(11/t)W$\) and with no simple path of more than \($g$\) edges. A family of graphs is emphtrimmable if for every constant \($t>0$\), there is a constant \($g\ge 0$\) such that every vertexweighted 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 polynomialtime approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axesparallel 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.

Rutter, I., Wolff, A.: Computing Large Matchings Fast. ACM Transactions on Algorithms. 7, article 1, 21 pages (2010).
In this paper we present algorithms for computing large matchings in 3regular graphs, graphs with maximum degree 3, and 3connected 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 bestknown algorithm for computing maximum matchings in general graphs, which runs in \($O(\sqrtnm)$\) time, where \($n$\) denotes the number of vertices and \($m$\) the number of edges of the given graph. For the classes of 3regular 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 3regular graphs and 3connected planar graphs with boundeddegree 2 and 4block trees, respectively, we show how to compute emphmaximum matchings in slightly superlinear time.

Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C.S., Spillner, A., Wolff, A.: Untangling a Planar Graph. Discrete Computational Geometry. 42, 542569 (2009).
A straightline drawing \($\delta$\) of a planar graph \($G$\) need not be plane, but can be made so by emphuntangling 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 NPhard to compute and to approximate. Our hardness results extend to a version of textsc1BendPointSetEmbeddability, a wellknown graphdrawing problem. par Further we define fix\($(G,\delta)=nshift(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 \($\sqrt((\log n)1)/\log \log n$\) vertices when untangling a drawing of an \($n$\)vertex graph \($G$\). If \($G$\) is outerplanar, the same algorithm fixes at least \($\sqrtn/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) \le \sqrtn2+1$\) and an \($n$\)vertex outerplanar graph \($H$\) and a drawing \($\delta_H$\) of \($H$\) with fix\($(H,\delta_H) \le 2 \sqrtn1+1$\). Thus our algorithm is asymptotically worstcase 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, 248260 (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, 2147 (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 NPhard in the most general of the new models. Nevertheless, we give a polynomialtime approximation scheme and a simple and efficient factor1/2 approximation algorithm for each of the new models. par Finally, we give experimental results based on the factor1/2 approximation algorithm to compare the models in practice. We also compare this algorithm experimentally to other algorithms suggested in the literature.