Am 10.11.2018 hatten Einrichtungen und Institute der Leibniz Universität Hannover im Rahmen des Novembers der Wissenschaft erneut die Möglichkeit, einen Einblick in ihre Forschung zu gewähren. Zusammen mit dem Forschungszentrum L3S von der Universität Hannover konnten das Institute for Sustainable Urbanism (ISU) der TU Braunschweig und 1KLANG®, die Marke der PROJEKTIONISTEN® GmbH, das Forschungsprojekt Data4UrbanMobility vorstellen.
Studenten, Schüler und andere Forschungsinteressierte konnten sich über die Ergebnisse in Bezug auf die entwickelten Apps und das Dashboard informieren (s. unter Ergebnisse: https://data4urbanmobility.l3s.uni-hannover.de/index.php/de/ergebnisse/).
Besonders vorgestellt werden konnte dabei die neue iOS-Version der MiC App, die nun auch über eine Apple Watch gesteuert werden kann.

Wir freuen uns über die zahlreichen Gespräche, die geführt werden konnten und die neuen Tester, die uns bei der Citizen Science App „MiC – Move in the City“ unterstützen möchten.

• Eliminating Crossings in Ordered Graphs. Agrawal, Akanksha; Cabello, Sergio; Kaufmann, Michael; Saurabh, Saket; Sharma, Roohani; Uno, Yushi; Wolff, Alexander in LIPIcs, H. Bodlaender (ed.) (2024).
• Constrained and Ordered Level Planarity Parameterized by the Number of Levels. Blažej, Vacláv; Klemz, Boris; Klesen, Felix; Sieper, Marie Diana; Wolff, Alexander; Zink, Johannes in LIPIcs, W. Mulzer, J. M. Phillips (eds.) (2024). (Vol. 293)
• The Parametrized Complexity of the Segment Number. Cornelsen, Sabine; Da Lozzo, Giordano; Grilli, Luca; Gupta, Siddharth; Kratochvíl, Jan; Wolff, Alexander in Lecture Notes in Computer Science, M. Bekos, M. Chimani (eds.) (2023). (Vol. 14466) 97–113.
• Planar L-Drawings of Directed Graphs. Chaplick, Steven; Chimani, Markus; Cornelsen, Sabine; Da Lozzo, Giordano; Nöllenburg, Martin; Patrignani, Maurizio; Tollis, Ioannis G.; Wolff, Alexander (2023). 2(1) 7:1–7:15.

  In this paper, we study drawings of directed graphs. We use the L-drawing standard where each edge is represented by a polygonal chain that consists of a vertical line segment incident to the source of the edge and a horizontal line segment incident to the target. par First, we consider planar L-drawings. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. We also show how to decide in linear time whether there exists a planar L-drawing of a plane directed graph with a fixed assignment of the edges to the four sides (top, bottom, left, and right) of the vertices. par Second, we consider upward- (resp.\ upward-rightward-) planar L-drawings. We provide upper bounds on the maximum number of edges of graphs admitting such drawings. Moreover, we characterize the directed st-graphs admitting an upward- (resp.\ upward-rightward-) planar L-drawing as exactly those admitting an embedding supporting a bitonic (resp.\ monotonically decreasing) st-ordering.
• Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees. Klawitter, Jonathan; Klesen, Felix; Niederer, Moritz; Wolff, Alexander in Lecture Notes in Computer Science, L. Gąsieniec (ed.) (2023). (Vol. 13878) 96–110.
• Morphing Rectangular Duals. Chaplick, Steven; Kindermann, Philipp; Klawitter, Jonathan; Rutter, Ignaz; Wolff, Alexander in Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (eds.) (2023). (Vol. 13764) 389–403.
• The Computational Complexity of the ChordLink Model. Kindermann, Philipp; Sauer, Jan; Wolff, Alexander (2023). 27(9) 759–767.

  In order to visualize well-clustered graphs with many intra-cluster but few inter-cluster edges, hybrid approaches have been proposed. For example, ChordLink draws the clusters as chord diagrams and embeds these into a node-link diagram that represents the overall structure of the clustered graph. The ChordLink approach consists of four steps; node replication, node permutation, node merging, and chord insertion. In this paper, we focus on the optimization problems defined by two of these steps. We show that the decision version of the problem defined by node permutation is NP-complete and present an efficient algorithm for a special case. For chord insertion, we show that it is NP-complete to decide whether a crossing-free placement of the chords exists. Moreover, it is APX-hard to minimize the number of crossings among the chords. Our results answer an open question posed by Angori, Didimo, Montecchiani, Pagliuca, and Tappini, who introduced ChordLink [TVCG 2021].
• Morphing Planar Graph Drawings Through 3D. Buchin, Kevin; Evans, Will; Frati, Fabrizio; Kostitsyna, Irina; Löffler, Maarten; Ophelders, Tim; Wolff, Alexander (2023). 2(1) 5:1–5:18.

  In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-line drawings of an \($n$\)-vertex planar graph, there exists a piecewise-linear crossing-free 3D morph with \($O(n^2)$\) steps that transforms one drawing into the other. We also give some evidence why it is difficult to obtain a linear lower bound (which exists in 2D) for the number of steps of a crossing-free 3D morph.
• Coloring Mixed and Directional Interval Graphs. Gutowski, Grzegorz; Mittelstädt, Florian; Rutter, Ignaz; Spoerhase, Joachim; Wolff, Alexander; Zink, Johannes in Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (eds.) (2023). (Vol. 13764) 418–431.
• Algorithms for Floor Planning with Proximity Requirements. Klawitter, Jonathan; Klesen, Felix; Wolff, Alexander in CCIS, D. J. Gerber, A. Nahmad, B. Bogosian, E. Pantazis, C. Miltiadis (eds.) (2022). (Vol. 1465) 151–171.
• Simple Algorithms for Partial and Simultaneous Rectangular Duals with Given Contact Orientations. Chaplick, Steven; Felsner, Stefan; Kindermann, Philipp; Klawitter, Jonathan; Rutter, Ignaz; Wolff, Alexander (2022). 919 66–74.

  A rectangular dual of a graph \($G$\) is a contact representation of \($G$\) by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The emphpartial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. The emphsimultaneous representation problem for rectangular duals asks whether two (or more) given graphs that share a subgraph admit rectangular duals that coincide on the shared subgraph. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. par We describe linear-time algorithms for the partial representation extension problem and the simultaneous representation problem for rectangular duals when each input graph is given together with a REL. Both algorithms are based on formulations as linear programs, yet they have geometric interpretations and can be seen as extensions of the classic algorithm by Kant and He that computes a rectangular dual for a given graph.
• The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs. Goeßmann, Ina; Klawitter, Jonathan; Klemz, Boris; Klesen, Felix; Kobourov, Stephen G.; Kryven, Myroslav; Wolff, Alexander; Zink, Johannes in Lecture Notes in Computer Science, M. Bekos, M. Kaufmann (eds.) (2022). (Vol. 13453) 16 pages.
• Minimum Rectilinear Polygons for Given Angle Sequences. Evans, William S.; Fleszar, Krzysztof; Kindermann, Philipp; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander (2022). 100(101820) 1–39.

  A rectilinear polygon is a simple polygon whose edges are axis-aligned. Walking counterclockwise on the boundary of such a polygon yields a sequence of left turns and right turns. The number of left turns always equals the number of right turns plus four. It is known that any such sequence can be realized by a rectilinear polygon. par In this paper, we consider the problem of finding realizations that minimize the perimeter or the area of the polygon or the area of the bounding box of the polygon. We show that all three problems are NP-hard in general. This answers an open question of Patrignani [CGTA 2001], who showed that it is NP-hard to minimize the area of the bounding box of an orthogonal drawing of a given planar graph. We also show that realizing a polyline within a bounding box of minimum area (or within a fixed given rectangle) is NP-hard. Then we consider the special cases of x-monotone and xy-monotone rectilinear polygons. For these, we can optimize the three objectives efficiently.
• Bounding and Computing Obstacle Numbers of Graphs. Balko, Martin; Chaplick, Steven; Ganian, Robert; Gupta, Siddharth; Hoffmann, Michael; Valtr, Pavel; Wolff, Alexander in LIPIcs, S. Chechik, G. Navarro, E. Rotenberg, G. Herman (eds.) (2022). (Vol. 244) 11:1–13.
• ClusterSets: Optimizing Planar Clusters in Categorical Point Data. Geiger, Jakob; Cornelsen, Sabine; Haunert, Jan-Henrik; Kindermann, Philipp; Mchedlidze, Tamara; Nöllenburg, Martin; Okamoto, Yoshio; Wolff, Alexander (2021). 40(3) 471–481.
• Drawing Graphs with Circular Arcs and Right-Angle Crossings. Chaplick, Steven; Förster, Henry; Kryven, Myroslav; Wolff, Alexander in LIPIcs, S. Albers (ed.) (2020). (Vol. 162) 21:1–14.
• Drawing Graphs on Few Lines and Few Planes. Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander (2020). 11(1) 433–475.

  We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many relations to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. par We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. par We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). par We pay special attention to planar graphs. For example, we show that there are qplanar graphs that can be drawn in 3-space on asymptotically fewer lines than in the plane.
• Finding Optimal Sequences for Area Aggregation---A* vs. Integer Linear Programming. Peng, Dongliang; Wolff, Alexander; Haunert, Jan-Henrik (2020). 7(1)

  To provide users with maps of different scales and to allow them to zoom in and out without losing context, automatic methods for map generalization are needed. We approach this problem for land-cover maps. Given two land-cover maps at two different scales, we want to find a sequence of small incremental changes that gradually transforms one map into the other. We assume that the two input maps consist of polygons, each of which belongs to a given land-cover type. Every polygon on the smaller-scale map is the union of a set of adjacent polygons on the larger-scale map. par In each step of the computed sequence, the smallest area is merged with one of its neighbors. We do not select that neighbor according to a prescribed rule but compute the whole sequence of pairwise merges at once, based on global optimization. We have proved that this problem is NP-hard. We formalize this optimization problem as that of finding a shortest path in a (very large) graph. We present the A\($^\star$\) algorithm and integer linear programming to solve this optimization problem. To avoid long computing times, we allow the two methods to return non-optimal results. In addition, we present a greedy algorithm as a benchmark. We tested the three methods with a dataset of the official German topographic database ATKIS. Our main result is that A\($^\star$\) finds optimal aggregation sequences for more instances than the other two methods within a given time frame.
• Bundled Crossings Revisited. Chaplick, Steven; van Dijk, Thomas C.; Kryven, Myroslav; Park, Ji-Won; Ravsky, Alexander; Wolff, Alexander (2020). 24(4) 621–655.

  An effective way to reduce clutter in a graph drawing that has (many) crossings is to group edges that travel in parallel into bundles. Each edge can participate in many such bundles. Any crossing in this bundled graph occurs between two bundles, i.e., as a bundled crossing. We consider the problem of bundled crossing minimization: A graph is given and the goal is to find a bundled drawing with at most \($k$\) bundled crossings. We show that the problem is NP-hard when we require a simple drawing. Our main result is an FPT algorithm (in \($k$\)) for simple circular layouts where vertices must be placed on a circle and edges must be drawn inside the circle. These results make use of the connection between bundled crossings and graph genus. We also consider bundling crossings in a given drawing, in particular for storyline visualizations.
• Variants of the Segment Number of a Graph. Okamoto, Yoshio; Ravsky, Alexander; Wolff, Alexander in Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.) (2019). (Vol. 11904) 430–443.
• Stick Graphs with Length Constraints. Chaplick, Steven; Kindermann, Philipp; Löffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes in Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.) (2019). (Vol. 11904) 3–17.
• Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity. Argyriou, Evmorfia; Cornelsen, Sabine; Förster, Henry; Kaufmann, Michael; Nöllenburg, Martin; Okamoto, Yoshio; Raftopoulou, Chrysanthi; Wolff, Alexander in Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.) (2018). (Vol. 11282) 509–523.
• Planar L-Drawings of Directed Graphs. Chaplick, Steven; Chimani, Markus; Cornelsen, Sabine; Da Lozzo, Giordano; Nöllenburg, Martin; Patrignani, Maurizio; Tollis, Ioannis G.; Wolff, Alexander in Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.) (2018). (Vol. 10692) 465–478.
• Improved Approximation Algorithms for Box Contact Representations. Bekos, Michael A.; van Dijk, Thomas C.; Fink, Martin; Kindermann, Philipp; Kobourov, Stephen; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander (2017). 77(3) 902–920.

  We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max-Crown, in which realizing each desired adjacency yields a certain profit. We present the first \($O(1)$\)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APX-complete on bipartite graphs of bounded maximum degree.
• Beyond Maximum Independent Set: An Extended Integer Programming Formulation for Point Labeling. Haunert, Jan-Henrik; Wolff, Alexander (2017). 6(11) article 342, 20 pages.

  Map labeling is a classical problem of cartography that has frequently been approached by combinatorial optimization. Given a set of features in a map and for each feature a set of label candidates, a common problem is to select an independent set of labels (that is, a labeling without label--label intersections) that contains as many labels as possible and at most one label for each feature. To obtain solutions of high cartographic quality, the labels can be weighted and one can maximize the total weight (rather than the number) of the selected labels. We argue, however, that when maximizing the weight of the labeling, the influences of labels on other labels are insufficiently addressed. Furthermore, in a maximum-weight labeling, the labels tend to be densely packed and thus the map background can be occluded too much. We propose extensions of an existing model to overcome these limitations. Since even without our extensions the problem is NP-hard, we cannot hope for an efficient exact algorithm for the problem. Therefore, we present a formalization of our model as an integer linear program (ILP). This allows us to compute optimal solutions in reasonable time, which we demonstrate both for randomly generated point sets and an existing data set of cities. Moreover, a relaxation of our ILP allows for a simple and efficient heuristic, which yielded near-optimal solutions for our instances.
• Block Crossings in Storyline Visualizations. van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander in Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.) (2016). (Vol. 9801) 382–398.
• Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends. Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander (2016). 20(1) 133–158.
• Multi-Sided Boundary Labeling. Kindermann, Philipp; Niedermann, Benjamin; Rutter, Ignaz; Schaefer, Marcus; Schulz, André; Wolff, Alexander (2016). 76(1) 225–258.

  In the emphBoundary Labeling problem, we are given a set of \($n$\) points, referred to as emphsites, inside an axis-parallel rectangle \($R$\), and a set of n pairwise disjoint rectangular labels that are attached to \($R$\) from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders, with at most one bend. In this paper, we study the emphMulti-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of \($R$\) (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.
• Minimum Rectilinear Polygons for Given Angle Sequences. Evans, William S.; Fleszar, Krzysztof; Kindermann, Philipp; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander in Lecture Notes in Computer Science, J. Akiyama, H. Ito, T. Sakai (eds.) (2016). (Vol. 9943) 105–119.
• Snapping Graph Drawings to the Grid Optimally. Löffler, Andre; van Dijk, Thomas C.; Wolff, Alexander in Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.) (2016). (Vol. 9801) 144–151.
• Matching Labels and Markers in Historical Maps: An Algorithm with Interactive Postprocessing. Budig, Benedikt; Dijk, Thomas C. van; Wolff, Alexander (2016). 2(4) 13:1–24.
• Drawing Graphs on Few Lines and Few Planes. Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.) (2016). (Vol. 9801) 166–180.
• Ordering Metro Lines by Block Crossings. Fink, Martin; Pupyrev, Sergey; Wolff, Alexander (2015). 19(1) 111–153.

  A problem that arises in drawings of transportation networks is to minimize the number of crossings between different transportation lines. While this can be done efficiently under specific constraints, not all solutions are visually equivalent. We suggest merging single crossings into emphblock crossings, that is, crossings of two neighboring groups of consecutive lines. Unfortunately, minimizing the total number of block crossings is NP-hard even for very simple graphs. We give approximation algorithms for special classes of graphs and an asymptotically worst-case optimal algorithm for block crossings on general graphs. Furthermore, we show that the problem remains NP-hard on planar graphs even if both the maximum degree and the number of lines per edge are bounded by constants; on trees, this restricted version becomes tractable.
• Colored Non-Crossing Euclidean Steiner Forest. Bereg, Sergey; Fleszar, Krzysztof; Kindermann, Philipp; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander in Lecture Notes in Computer Science, K. Elbassioni, K. Makino (eds.) (2015). (Vol. 9472) 429–441.
• Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends. Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander in Lecture Notes in Computer Science, M. S. Rahman, E. Tomita (eds.) (2015). (Vol. 8973) 222–233.
• Approximating Minimum Manhattan Networks in Higher Dimensions. Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen; Spoerhase, Joachim; Wolff, Alexander (2015). 71(1) 36–52.

  We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called emphterminals in~\($\mathbbR^d$\), find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair's Manhattan (that is, \($L_1$\)-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless \($\cal P = \cal NP$\)). Approximation algorithms are known for 2D, but not for 3D. par We present, for any fixed dimension~\($d$\) and any \($\epsilon>0$\), an \($O(n^\epsilon)$\)-approxi-ma-tion algorithm. For 3D, we also give a \($4(k-1)$\)-approximation algorithm for the case that the terminals are contained in the union of \($k \ge 2$\) parallel planes.
• Concentric Metro Maps. Fink, Martin; Lechner, Magnus; Wolff, Alexander (2014).
• Point Labeling with Sliding Labels in Interactive Maps. Schwartges, Nadine; Haunert, Jan-Henrik; Wolff, Alexander; Zwiebler, Dennis in Lecture Notes in Geoinformation and Cartography, J. Huerta, S. Schade, C. Granell (eds.) (2014). 295–310.
• Semantic Word Cloud Representations: Hardness and Approximation Algorithms. Barth, Lukas; Fabrikant, Sara Irina; Kobourov, Stephen; Lubiw, Anna; Nöllenburg, Martin; Okamoto, Yoshio; Pupyrev, Sergey; Squarcella, Claudio; Ueckerdt, Torsten; Wolff, Alexander in Lecture Notes in Computer Science, A. Pardo, A. Viola (eds.) (2014). (Vol. 8392) 514–525.
• Guest Editors’ Foreword (Special Issue of Selected Papers from the 21st Int. Symp. Graph Drawing). Wismath, Stephen; Wolff, Alexander (2014). 18(2) 174–175.
• Watch Your Data Structures. Peng, Dongliang; Wolff, Alexander (2014). 10 pages.
• Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation. Fink, Martin; Haunert, Jan-Henrik; Spoerhase, Joachim; Wolff, Alexander (2013). 19(12) 2326–2335.
• Drawing Metro Maps using Bézier Curves. Fink, Martin; Haverkort, Herman; Nöllenburg, Martin; Roberts, Maxwell; Schuhmann, Julian; Wolff, Alexander in Lecture Notes in Computer Science, W. Didimo, M. Patrignani (eds.) (2013). (Vol. 7704) 463–474.
• Proceedings of the 21st International Symposium on Graph Drawing (GD’13) Wismath, Stephen; Wolff, Alexander in Lecture Notes in Computer Science (2013). (Vol. 8242) Springer-Verlag.
• Optimizing Active Ranges for Point Selection in Dynamic Maps. Schwartges, Nadine; Allerkamp, Dennis; Haunert, Jan-Henrik; Wolff, Alexander (2013).
• Approximating the Generalized Minimum Manhattan Network Problem. Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen G.; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Lecture Notes in Computer Science, L. Cai, S.-W. Cheng, T.-W. Lam (eds.) (2013). (Vol. 8283) 722–732.
• Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Fink, Martin; Haunert, Jan-Henrik; Mchedlidze, Tamara; Spoerhase, Joachim; Wolff, Alexander in Lecture Notes in Computer Science, M. S. Rahman, S.- ichi Nakano (eds.) (2012). (Vol. 7157) 186–197.
• Augmenting the Connectivity of Planar and Geometric Graphs. Rutter, Ignaz; Wolff, Alexander (2012). 16(2) 599–628.

  In this paper we study connectivity augmentation problems. Given a connected graph~\($G$\) with some desirable property, we want to make~\($G$\) 2-vertex connected (or 2-edge connected) by adding edges such that the resulting graph keeps the property. The aim is to add as few edges as possible. The property that we consider is planarity, both in an abstract graph-theoretic and in a geometric setting, where vertices correspond to points in the plane and edges to straight-line segments. par We show that it is NP-hard to find a minimum-cardinality augmentation that makes a planar graph 2-edge connected. For making a planar graph 2-vertex connected this was known. We further show that both problems are hard in the geometric setting, even when restricted to trees. The problems remain hard for higher degrees of connectivity. On the other hand we give polynomial-time algorithms for the special case of convex geometric graphs. par We also study the following related problem. Given a planar (plane geometric) graph~\($G$\), two vertices~\($s$\) and~\($t$\) of~\($G$\), and an integer~\($c$\), how many edges have to be added to~\($G$\) such that~\($G$\) is still planar (plane geometric) and contains \($c$\) edge- (or vertex-) disjoint \($s$\)--\($t$\) paths? For the planar case we give a linear-time algorithm for \($c=2$\). For the plane geometric case we give optimal worst-case bounds for \($c=2$\); for \($c=3$\) we characterize the cases that have a solution.
• Putting Data on the Map Kobourov, Stephen; Wolff, Alexander; van Ham, Frank in Dagstuhl Reports (2012). (Vol. 2) 51–76. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Cover Contact Graphs. Atienza, Nieves; de Castro, Natalia; Cortés, Carmen; Garrido, M. Ángeles; Grima, Clara I.; Hernández, Gregorio; Márquez, Alberto; Moreno-González, Auxiliadora; Nöllenburg, Martin; Portillo, José Ramon; Reyes, Pedro; Valenzuela, Jesús; Villar, Maria Trinidad; Wolff, Alexander (2012). 3(1)

  We study problems that arise in the context of covering certain geometric objects called seeds (e.g., points or disks) by a set of other geometric objects called cover (e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pairwise disjoint, respectively, but they can touch. We call the contact graph of a cover a cover contact graph (CCG). par We are interested in three types of tasks, both in the general case and in the special case of seeds on a line: (a) deciding whether a given seed set has a connected CCG, (b) deciding whether a given graph has a realization as a CCG on a given seed set, and (c) bounding the sizes of certain classes of CCG's. par Concerning (a) we give efficient algorithms for the case that seeds are points and show that the problem becomes hard if seeds and covers are disks. Concerning (b) we show that this problem is hard even for point seeds and disk covers (given a fixed correspondence between graph vertices and seeds). Concerning (c) we obtain upper and lower bounds on the number of CCG's for point seeds.
• Algorithms for Labeling Focus Regions. Fink, Martin; Haunert, Jan-Henrik; Schulz, André; Spoerhase, Joachim; Wolff, Alexander (2012). 18(12) 2583–2592.

  In this paper, we investigate the problem of labeling point sites in focus regions of maps or diagrams. This problem occurs, for example, when the user of a mapping service wants to see the names of restaurants or other POIs in a crowded downtown area but keep the overview over a larger area. Our approach is to place the labels at the boundary of the focus region and connect each site with its label by a linear connection, which is called a leader. In this way, we move labels from the focus region to the less valuable context region surrounding it. In order to make the leader layout well readable, we present algorithms that rule out crossings between leaders and optimize other characteristics such as total leader length and distance between labels. par This yields a new variant of the boundary labeling problem, which has been studied in the literature. Other than in traditional boundary labeling, where leaders are usually schematized polylines, we focus on leaders that are either straight-line segments or Bézier curves. Further, we present algorithms that, given the sites, find a position of the focus region that optimizes the above characteristics. par We also consider a variant of the problem where we have more sites than space for labels. In this situation, we assume that the sites are prioritized by the user. Alternatively, we take a new facility-location perspective which yields a clustering of the sites. We label one representative of each cluster. If the user wishes, we apply our approach to the sites within a cluster, giving details on demand.
• Approximating Minimum Manhattan Networks in Higher Dimensions. Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen; Spoerhase, Joachim; Wolff, Alexander in Lecture Notes in Computer Science, C. Demetrescu, M. M. Halldórsson (eds.) (2011). (Vol. 6942) 49–60.
• How Alexander the Great Brought the Greeks Together While Inflicting Minimal Damage to the Barbarians. de Berg, Mark; Gerrits, Dirk; Khosravi, Amirali; Rutter, Ignaz; Tsirogiannis, Constantinos; Wolff, Alexander (2010). 73–76.
• Optimal and Topologically Safe Simplification of Building Footprints. Haunert, Jan-Henrik; Wolff, Alexander (2010). 192–201.
• The Traveling Salesman Problem Under Squared Euclidean Distances. de Berg, Marc; van Nijnatten, Fred; Sitters, René; Woeginger, Gerhard J.; Wolff, Alexander J.-Y. Marion, T. Schwentick (eds.) (2010). 239–250.
• Area aggregation in map generalisation by mixed-integer programming. Haunert, Jan-Henrik; Wolff, Alexander (2010). 24(12) 1871–1897.

  Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.
• Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability. Buchin, Kevin; Buchin, Maike; Byrka, Jaroslaw; Nöllenburg, Martin; Okamoto, Yoshio; Silveira, Rodrigo I.; Wolff, Alexander in Lecture Notes in Computer Science, I. G. Tollis, M. Patrignani (eds.) (2009). (Vol. 5417) 324–335.
• Untangling a Planar Graph. Spillner, Andreas; Wolff, Alexander in Lecture Notes in Computer Science, V. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková (eds.) (2008). (Vol. 4910) 473–484.
• Optimizing Active Ranges for Consistent Dynamic Map Labeling. Been, Ken; Nöllenburg, Martin; Poon, Sheung-Hung; Wolff, Alexander (2008). 10–19.
• Augmenting the Connectivity of Planar and Geometric Graphs. Rutter, Ignaz; Wolff, Alexander in Electronic Notes in Discrete Mathematics (2008). (Vol. 31) 53–56.
• Morphing Polylines: A Step Towards Continuous Generalization. Nöllenburg, Martin; Merrick, Damian; Wolff, Alexander; Benkert, Marc (2008). 32(4) 248–260.

  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.
• Constructing the City Voronoi Diagram Faster. Görke, Robert; Shin, Chan-Su; Wolff, Alexander (2008). 18(4) 275–294.

  Given a set \($P$\) of \($n$\) point sites in the plane, the city Voronoi diagram subdivides the plane into the Voronoi regions of the sites, with respect to the city metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating trans- portation network that consists of \($c$\) non-intersecting axis-parallel line segments. We describe an algorithm that constructs the city Voronoi diagram (including quickest path information) using \($O((c + n) polylog(c + n))$\) time and storage by means of a wavefront expansion. For \($c in \Omega(\sqrtn \log^3 n)$\) our algorithm is faster than an algorithm by Aichholzer et al., which takes \($O(n \log n + c^2 \log c)$\) time.
• Constructing Interference-Minimal Networks. Benkert, Marc; Gudmundsson, Joachim; Haverkort, Herman; Wolff, Alexander (2008). 40(3) 179–194.

  A wireless ad-hoc network can be represented as a graph in which the nodes represent wireless devices, and the links represent pairs of nodes that communicate directly by means of radio signals. The emphinterference caused by a link between two nodes~\($u$\) and~\($v$\) can be defined as the number of other nodes that may be disturbed by the signals exchanged by \($u$\) and~\($v$\). Given the position of the nodes in the plane, links are to be chosen such that the maximum interference caused by any link is limited and the network fulfills desirable properties such as connectivity, bounded dilation or bounded link diameter. We give efficient algorithms to find the links in two models. In the first model, the signal sent by~\($u$\) to~\($v$\) reaches exactly the nodes that are not farther from~\($u$\) than~\($v$\) is. In the second model, we assume that the boundary of a signal's reach is not known precisely and that our algorithms should therefore be based on acceptable estimations. The latter model yields faster algorithms.
• Computing Large Matchings Fast. Rutter, Ignaz; Wolff, Alexander (2008). 183–192.
• Optimal Simplification of Building Ground Plans. Haunert, Jan-Henrik; Wolff, Alexander in Int. Archives of Photogrammetry, Remote Sensing and Spatial Informat. Sci. (2008). (Vol. XXXVII, Part B2) 373–378.
• Morphing Polygonal Lines: A Step Towards Continuous Generalization. Merrick, Damian; Nöllenburg, Martin; Wolff, Alexander; Benkert, Marc (2007). 390–399.
• Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps. Benkert, Marc; Nöllenburg, Martin; Uno, Takeaki; Wolff, Alexander in Lecture Notes in Computer Science, M. Kaufmann, D. Wagner (eds.) (2007). (Vol. 4372) 270–281.
• Constructing Optimal Highways. Ahn, Hee-Kap; Alt, Helmut; Asano, Tetsuo; Bae, Sang Won; Brass, Peter; Cheong, Otfried; Knauer, Christian; Na, Hyeon-Suk; Shin, Chan-Su; Wolff, Alexander in Conferences in Research and Practice in Information Technology, B. Jay, J. Gudmundsson (eds.) (2007). (Vol. 65) 7–14.
• Geometric Networks and Metric Space Embeddings Gudmundsson, Joachim; Klein, Rolf; Narasimhan, Giri; Smid, Michiel; Wolff, Alexander in Dagstuhl Seminar Proceedings (2007). (Vol. 06481) Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem. Benkert, Marc; Gudmundsson, Joachim; Knauer, Christian; Moet, Esther; van Oostrum, René; Wolff, Alexander (2006). 141–144.
• The Minimum Manhattan Network Problem: Approximations and Exact Solutions. Benkert, Marc; Wolff, Alexander; Widmann, Florian; Shirabe, Takeshi (2006). 35(3) 188–208.

  Given a set of points in the plane and a constant \($t\ge 1$\), a Euclidean \($t$\)-emphspanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most~\($t$\). Such networks have applications in transportation or communication network design and have been studied extensively. par In this paper we study 1-spanners under the Manhattan (or \($L_1$\)-) metric. Such networks are called emphManhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an \($x$\)- and \($y$\)-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e. Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set \($P$\) of \($n$\) points, our algorithm computes in \($O(n \log n)$\) time and linear space a Manhattan network for \($P$\) whose length is at most 3 times the length of an MMN of \($P$\). par We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets.
• Generalization of Land Cover Maps by Mixed Integer Programming. Haunert, Jan-Henrik; Wolff, Alexander (2006). 75–82.
• Farthest-Point Queries with Geometric and Combinatorial Constraints. Daescu, Ovidiu; Mi, Ningfang; Shin, Chan-Su; Wolff, Alexander (2006). 33(3) 174–185.

  In this paper we discuss farthest-point problems in which a set or sequence \($S$\) of \($n$\) points in the plane is given in advance and can be preprocessed to answer various queries efficiently. First, we give a data structure that can be used to compute the point farthest from a query line segment in \($O(\log^2 n)$\) time. Our data structure needs \($O(n \log n)$\) space and preprocessing time. To the best of our knowledge no solution to this problem has been suggested yet. Second, we show how to use this data structure to obtain an output-sensitive query-based algorithm for polygonal path simplification. Both results are based on a series of data structures for fundamental farthest-point queries that can be reduced to each other.
• A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem. Benkert, Marc; Gudmundsson, Joachim; Knauer, Christian; Moet, Esther; van Oostrum, René; Wolff, Alexander in Lecture Notes in Computer Science, D. Z. Chen, D.-T. Lee (eds.) (2006). (Vol. 4112) 166–175.
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation. Benkert, Marc; Widmann, Florian; Wolff, Alexander in Lecture Notes in Computer Science, J. Akiyama, M. Kano, X. Tan (eds.) (2005). (Vol. 3742) 16–28.
• Optimal Spanners for Axis-Aligned Rectangles. Asano, Tetsuo; de Berg, Mark; Cheong, Otfried; Everett, Hazel; Haverkort, Herman; Katoh, Naoki; Wolff, Alexander (2005). 30(1) 59–77.

  The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the \($L_1$\)-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their \($L_1$\)-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles. par We study the following problem: given \($n$\) non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i)~for arbitrary graphs, the problem is NP-hard; (ii)~for trees, we can solve the problem by linear programming on \($O(n^2)$\)~variables and constraints; (iii)~for paths, we can solve the problem in time~\($O(n^3\log n)$\); (iv)~for rectangles sorted vertically along a path, the problem can be solved in \($O(n^2)$\) time, and a \($(1+\varepsilon)$\)-approximation can be computed in linear time.
• Geometrische Netzwerke und ihre Visualisierung. Wolff, Alexander (2005, June).
• Spanning Trees with Few Crossings in Geometric and Topological Graphs. Knauer, Christian; Schramm, Étienne; Spillner, Andreas; Wolff, Alexander (2005). 195–198.
• Constructing Interference-Minimal Networks. Benkert, Marc; Gudmundsson, Joachim; Haverkort, Herman; Wolff, Alexander (2005). 203–206.
• Configurations with Few Crossings in Topological Graphs. Knauer, Christian; Schramm, Étienne; Spillner, Andreas; Wolff, Alexander in Lecture Notes in Computer Science, X. Deng, D.-Z. Du (eds.) (2005). (Vol. 3827) 604–613.

  In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph \($G$\) such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, \($s$\)--\($t$\) paths, cycles, matchings, and \($\kappa$\)-factors for \($\kappa \in \1,2\$\). We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of \(k^1-\varepsilon\) for any \(\varepsilon > 0\), where \($k$\) is the number of crossings in \($G$\). We then show that the problems are fixed-parameter tractable if we use the number of crossings in the given graph as the parameter. Finally we present a simple but effective heuristic for spanning trees.
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation. Benkert, Marc; Widmann, Florian; Wolff, Alexander (2004). 85–86.
• Optimal Spanners for Axis-Aligned Rectangles. Asano, Tetsuo; de Berg, Mark; Cheong, Otfried; Everett, Hazel; Haverkort, Herman; Katoh, Naoki; Wolff, Alexander (2004). 97–100.
• Algorithms for the Placement of Diagrams on Maps. van Kreveld, Marc; Schramm, Étienne; Wolff, Alexander D. Pfoder, I. F. Cruz, M. Ronthaler (eds.) (2004). 222–231.

  This paper discusses a variety of ways to place diagrams like pie charts on maps, in particular, administrative subdivisions. The different ways come from different models of the placement problem: a diagram of one region should cover other regions, roads or boundaries as little as possible. In total we present six models for diagram placement. We outline three different algorithmic approaches and discuss the efficiency of each approach for the different models, and also for different types of diagrams (rectangular, circular, same or different sizes). We have implemented an algorithm for each model and show the resulting diagram placements on a number of maps. Our evaluation gives a first indication which model is best for aesthetically good diagram placement.
• Farthest-Point Queries with Geometric and Combinatorial Constraints. Daescu, Ovidiu; Mi, Ningfang; Shin, Chan-Su; Wolff, Alexander (2004). 45–48.
• Facility Location and the Geometric Minimum-Diameter Spanning Tree. Gudmundsson, Joachim; Haverkort, Herman; Park, Sang-Min; Shin, Chan-Su; Wolff, Alexander (2004). 27(1) 87–106.

  Let \($P$\) be a set of \($n$\) points in the plane. The geometric minimum-diameter spanning tree (MDST) of \($P$\) is a tree that spans \($P$\) and minimizes the Euclidian length of the longest path. It is known that there is always a mono- or a dipolar MDST, i.e. a MDST with one or two nodes of degree greater 1, respectively. The more difficult dipolar case can so far only be solved in slightly subcubic time. par This paper has two aims. First, we present a solution to a new data structure for facility location, the minimum-sum dipolar spanning tree (MSST), that mediates between the minimum-diameter dipolar spanning tree and the discrete two-center problem (2CP) in the following sense: find two centers \($p$\) and \($q$\) in \($P$\) that minimize the sum of their distance plus the distance of any other point (client) to the closer center. This is of interest if the two centers do not only serve their customers (as in the case of the 2CP), but frequently have to exchange goods or personnel between themselves. We give an \($O(n^2 \log n)$\)-time algorithm for this problem. A slight modification of our algorithm yields a factor-4/3 approximation of the MDST. par Second, we give two fast approximation schemes for the MDST, i.e. factor-(\($1+\varepsilon$\)) approximation algorithms. One uses a grid and takes \($O^*(E^6-1/3+n)$\) time, where \($E=1/\varepsilon$\) and the \($O^*$\)-notation hides terms of type \($O(\log^O(1) E)$\). The other uses the well-separated pair decomposition and takes \($O(n E^3 + E n \log n)$\) time. A combination of the two approaches runs in \($O^*(E^5 + n)$\) time. Both schemes can also be applied to MSST and 2CP.
• Labeling Points with Weights. Poon, Sheung-Hung; Shin, Chan-Su; Strijk, Tycho; Uno, Takeaki; Wolff, Alexander (2003). 38(2) 341–362.

  Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups; fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. par We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling \($n$\) points with unit-height rectangles. We show how an \($O(n\log n)$\)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is \($(2+\varepsilon)$\), it runs in \($O(n^2/\varepsilon)$\) time and uses \($O(n/\varepsilon)$\) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. par For slider models we also investigate some special cases, namely (a)~the number of different point weights is bounded, (b)~all labels are unit squares, and (c)~the ratio between maximum and minimum label height is bounded.
• A Simple Factor-2/3 Approximation Algorithm for Two-Circle Point Labeling. Wolff, Alexander; Thon, Michael; Xu, Yinfeng (2002). 12(4) 269–281.

  Given a set \($P$\) of \($n$\) points in the plane, the two-circle point-labeling problem consists of placing \($2n$\) uniform, non-intersecting, maximum-size open circles such that each point touches exactly two circles. par It is known that this problem is NP-hard to approximate. In this paper we give a simple algorithm that improves the best previously known approximation factor from \($4/(1+\sqrt33) \approx 0.5931$\) to 2/3. The main steps of our algorithm are as follows. We first compute the Voronoi diagram, then label each point emphoptimally within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size. We keep the \($O(n \log n)$\) time and \($O(n)$\) space bounds of the previously best algorithm.
• A Tutorial for Designing Flexible Geometric Algorithms. Kapoor, Vikas; Kühl, Dietmar; Wolff, Alexander (2002). 33(1) 52–70.

  The implementation of an algorithm is faced with the issues of efficiency, flexibility, and ease-of-use. In this paper we suggest a design concept that greatly increases the flexibility of an implementation without sacrificing ease-of-use and efficiency. par We demonstrate the advantages of our concept through a C++ implementation of a simple rectangle-intersection algorithm, which follows the well-known sweep-line paradigm. We lead the reader, who should be familiar with C++ and its template mechanism, from a naive interface in a step-by-step guide to an interface offering full flexibility. The gain in flexibility can reduce the overall implementation effort by facilitating code reuse. Reusability in turn helps to achieve correctness simply because more users mean more testing. par Though most of the ingredients of our concept have already been suggested elsewhere, to our knowledge this is the first time that they are applied vigorously in a geometric setting. We include a thorough experimental analysis on random and real-world data.
• Towards an Evaluation of Quality for Names Placement Methods. van Dijk, Steven; van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander (2002). 16(7) 641–661.

  The cartographic labeling problem is the problem of placing text on a map. This includes the positioning of the labels, and determining the shape in the case of line and area feature labels. There are many rules and customs that describe aspects of good label placement, like readability and clear association. This paper gives a classification of most label placement rules, and formalizes them into a function that can serve as a quality measure for label placement. If such a function is implemented, it allows to compare the output of different label placement programs. We give a simple and a more refined example of the quality function.
• Three Rules Suffice for Good Label Placement. Wagner, Frank; Wolff, Alexander; Kapoor, Vikas; Strijk, Tycho (2001). 30(2) 334–349.

  The general label-placement problem consists in labeling a set of features (points, lines, regions) given a set of candidates (rectangles, circles, ellipses, irregularly shaped labels) for each feature. The problem arises when annotating classical cartographical maps, diagrams, or graph drawings. The size of a labeling is the number of features that receive pairwise nonintersecting candidates. Finding an optimal solution, i.e., a labeling of maximum size, is NP-hard. par We present an approach to attack the problem in its full generality. The key idea is to separate the geometric part from the combinatorial part of the problem. The latter is captured by the conflict graph of the candidates. We present a set of rules that simplify the conflict graph without reducing the size of an optimal solution. Combining the application of these rules with a simple heuristic yields near-optimal solutions. We study competing algorithms and do a thorough empirical comparison on point-labeling data. The new algorithm we suggest is fast, simple, and effective.
• Labeling Points with Circles. Strijk, Tycho; Wolff, Alexander (2001). 11(2) 181–195.

  We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50 % to about 1/20. At the same time, our algorithm keeps the \($O(n \log n)$\) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.
• A Better Lower Bound for Two-Circle Point Labeling. Wolff, Alexander; Thon, Michael; Xu, Yinfeng in Lecture Notes in Computer Science, D. Lee, S.-H. Teng (eds.) (2000). (Vol. 1969) 422–431.
• Towards an Evaluation of Quality for Label Placement Methods. van Dijk, Steven; van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander (1999). 905–913.

  The cartographic labeling problem is the problem of placing text on a map. It is composed of two phases. In the first, the question which map features should in principle receive a label is settled and the style (i.e.\ color and font) of these labels is determined. The second phase consists of the actual label placement. In this phase for each feature one has to decide whether there is in fact sufficient space and, if yes, the best location and shape of the label must be determined. This paper proposes a quality measure for the result of the second phase, allowing the comparison of label placement programs.
• Point Labeling with Sliding Labels. van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander (1999). 13(1) 21–47.

  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.
• A Combinatorial Framework for Map Labeling. Wagner, Frank; Wolff, Alexander in Lecture Notes in Computer Science, S. H. Whitesides (ed.) (1999). (Vol. 1547) 316–331.
• Automated Label Placement in Theory and Practice. Technical Report (PhD dissertation), Wolff, Alexander (1999, May).
• A Practical Map Labeling Algorithm. Wagner, Frank; Wolff, Alexander (1997). 7(5--6) 387–404.

  The Map Labeling problem is a classical problem of cartography. There is a theoretically optimal approximation algorithm \($A$\). Unfortunately \($A$\) is useless in practice as it typically produces results that are intolerably far off the optimal size. On the other hand there are heuristics with good practical results. In this paper we present an algorithm \($B$\) that (a) guarantees the optimal approximation quality and runtime behaviour of \($A$\), and (b) yields results significantly closer to the optimum than the best heuristic known so far. The sample data used in the experimental evaluation consists of three different classes of random problems and a selection of problems arising in the production of groundwater quality maps by the authorities of the City of Munich.
• The Map-Labeling Bibliography. Wolff, Alexander; Strijk, Tycho (1996).
• Map Labeling Heuristics: Provably Good and Practically Useful. Wagner, Frank; Wolff, Alexander (1995). 109–118.
• Map Labeling. Technical Report (Master thesis), Wolff, Alexander PhD thesis, Fachbereich Mathematik und Informatik, Freie Universität Berlin. (1995, May).