Veröffentlichungen (nach Typ)

[ Article ]
[ Incollection ]
[ Inproceedings ]
[ Mastersthesis ]
[ Misc ]
[ PhD thesis ]
[ Proceedings ]

Article[ to top ]

Layered Drawing of Undirected Graphs with Generalized Port Constraints Zink, Johannes; Walter, Julian; Baumeister, Joachim; Wolff, Alexander in Computational Geometry: Theory and Applications (2022). 105--106(101886) 1–29.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
The aim of this research is a practical method to draw cable plans of complex machines. Such plans consist of electronic components and cables connecting specific ports of the components. Since the machines are configured for each client individually, cable plans need to be drawn automatically. The drawings must be well readable so that technicians can use them to debug the machines. In order to model plug sockets, we introduce port groups; within a group, ports can change their position (which we use to improve the aesthetics of the layout), but together the ports of a group must form a contiguous block. par We approach the problem of drawing such cable plans by extending the well-known Sugiyama framework such that it incorporates ports and port groups. Since the framework assumes directed graphs, we propose several ways to orient the edges of the given undirected graph. We compare these methods experimentally, both on real-world data and synthetic data that carefully simulates real-world data. We measure the aesthetics of the resulting drawings by counting bends and crossings. Using these metrics, we experimentally compare our approach to Kieler [JVLC 2014], a library for drawing graphs in the presence of port constraints. Our method produced 10--30 % fewer crossings, while it performed equally well or slightly worse than Kieler with respect to the number of bends and the time used to compute a drawing.

@article{zwbw-ldugg-CGTA22, abstract = {The aim of this research is a practical method to draw cable plans of complex machines. Such plans consist of electronic components and cables connecting specific ports of the components. Since the machines are configured for each client individually, cable plans need to be drawn automatically. The drawings must be well readable so that technicians can use them to debug the machines. In order to model plug sockets, we introduce port groups; within a group, ports can change their position (which we use to improve the aesthetics of the layout), but together the ports of a group must form a contiguous block. \par We approach the problem of drawing such cable plans by extending the well-known Sugiyama framework such that it incorporates ports and port groups. Since the framework assumes directed graphs, we propose several ways to orient the edges of the given undirected graph. We compare these methods experimentally, both on real-world data and synthetic data that carefully simulates real-world data. We measure the aesthetics of the resulting drawings by counting bends and crossings. Using these metrics, we experimentally compare our approach to Kieler [JVLC 2014], a library for drawing graphs in the presence of port constraints. Our method produced 10–30 \% fewer crossings, while it performed equally well or slightly worse than Kieler with respect to the number of bends and the time used to compute a drawing.}, author = {Zink, Johannes and Walter, Julian and Baumeister, Joachim and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {port_constraints}, number = 101886, pages = {1–29}, title = {Layered Drawing of Undirected Graphs with Generalized Port Constraints}, volume = {105–106}, year = 2022 }
Simple Algorithms for Partial and Simultaneous Rectangular Duals with Given Contact Orientations Chaplick, Steven; Felsner, Stefan; Kindermann, Philipp; Klawitter, Jonathan; Rutter, Ignaz; Wolff, Alexander in Theoretical Computer Science (2022). 919 66–74.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
- [ video ]
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 \emph{partial 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 \emph{simultaneous 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.

@article{cfkkrw-sapsr-TCS22, abstract = {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 \emph{partial 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 \emph{simultaneous 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.}, author = {Chaplick, Steven and Felsner, Stefan and Kindermann, Philipp and Klawitter, Jonathan and Rutter, Ignaz and Wolff, Alexander}, journal = {Theoretical Computer Science}, keywords = {simultaneous_representation}, pages = {66–74}, title = {Simple Algorithms for Partial and Simultaneous Rectangular Duals with Given Contact Orientations}, volume = 919, year = 2022 }
Minimum Rectilinear Polygons for Given Angle Sequences Evans, William S.; Fleszar, Krzysztof; Kindermann, Philipp; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander in Computational Geometry: Theory and Applications (2022). 100(101820) 1–39.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
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.

@article{efkssw-mrpga-CGTA22, abstract = {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.}, author = {Evans, William S. and Fleszar, Krzysztof and Kindermann, Philipp and Saeedi, Noushin and Shin, Chan-Su and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {myown}, number = 101820, pages = {1–39}, title = {Minimum Rectilinear Polygons for Given Angle Sequences}, volume = 100, year = 2022 }
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 in Comput. Graphics Forum (2021). 40(3) 471–481.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ video ]
@article{gchkmnow-coplc-EuroVis21, author = {Geiger, Jakob and Cornelsen, Sabine and Haunert, Jan-Henrik and Kindermann, Philipp and Mchedlidze, Tamara and N{\"o}llenburg, Martin and Okamoto, Yoshio and Wolff, Alexander}, journal = {Comput. Graphics Forum}, keywords = {myown}, number = 3, pages = {471–481}, title = {ClusterSets: Optimizing Planar Clusters in Categorical Point Data}, volume = 40, year = 2021 }
Angle Covers: Algorithms and Complexity Evans, William; Gethner, Ellen; Spalding-Jamieson, Jack; Wolff, Alexander in Journal of Graph Algorithms & Applications (2021). 25(2) 643–661.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@article{egsw-acac-JGAA21, author = {Evans, William and Gethner, Ellen and Spalding-Jamieson, Jack and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 2, pages = {643–661}, title = {Angle Covers: Algorithms and Complexity}, volume = 25, year = 2021 }
Finding Optimal Sequences for Area Aggregation---A* vs. Integer Linear Programming Peng, Dongliang; Wolff, Alexander; Haunert, Jan-Henrik in ACM Transactions on Spatial Algorithms and Systems (2020). 7(1)
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{pwh-fosaa-TSAS20, abstract = {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.}, author = {Peng, Dongliang and Wolff, Alexander and Haunert, Jan-Henrik}, journal = {ACM Transactions on Spatial Algorithms and Systems}, keywords = {type_change}, note = {article 4 (40 pages)}, number = 1, title = {Finding Optimal Sequences for Area Aggregation—{A}* vs.\ Integer Linear Programming}, volume = 7, year = 2020 }
Bundled Crossings Revisited Chaplick, Steven; van Dijk, Thomas C.; Kryven, Myroslav; Park, Ji-Won; Ravsky, Alexander; Wolff, Alexander in Journal of Graph Algorithms & Applications (2020). 24(4) 621–655.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
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.

@article{cdkprw-bcr-JGAA20, abstract = {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.}, author = {Chaplick, Steven and van Dijk, Thomas C. and Kryven, Myroslav and Park, Ji-Won and Ravsky, Alexander and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {storyline_visualization}, number = 4, pages = {621–655}, title = {Bundled Crossings Revisited}, volume = 24, year = 2020 }
Stick Graphs with and without Length Constraints Chaplick, Steven; Kindermann, Philipp; Löffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes in Journal of Graph Algorithms & Applications (2020). 24(4) 657–681.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
Stick graphs are intersection graphs of horizontal and vertical line seg- ments that all touch a line of slope ��1 and lie above this line. De Luca et al. [GD'18] considered the recognition problem of stick graphs when no order is given (STICK), when the order of either one of the two sets is given (STICK$$_A$$), and when the order of both sets is given (STICK$$_{AB}$$). They showed how to solve STICK$$_{AB}$$ efficiently. par In this paper, we improve the running time of their algorithm, and we solve STICK$$_A$$ efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of STICK, STICK$$_A$$, and STICK$$_{AB}$$ are all NP-complete. On the positive side, we give an efficient solution for STICK$$_{AB}$$ with fixed stick lengths if there are no isolated vertices.

@article{ckltwzz-sglc-JGAA20, abstract = {Stick graphs are intersection graphs of horizontal and vertical line seg- ments that all touch a line of slope ��1 and lie above this line. De Luca et al. [GD'18] considered the recognition problem of stick graphs when no order is given (STICK), when the order of either one of the two sets is given (STICK$_A$), and when the order of both sets is given (STICK$_{AB}$). They showed how to solve STICK$_{AB}$ efficiently. \par In this paper, we improve the running time of their algorithm, and we solve STICK$_A$ efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of STICK, STICK$_A$, and STICK$_{AB}$ are all NP-complete. On the positive side, we give an efficient solution for STICK$_{AB}$ with fixed stick lengths if there are no isolated vertices.}, author = {Chaplick, Steven and Kindermann, Philipp and L{\"o}ffler, Andre and Thiele, Florian and Wolff, Alexander and Zaft, Alexander and Zink, Johannes}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 4, pages = {657–681}, title = {Stick Graphs with and without Length Constraints}, volume = 24, year = 2020 }
Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Journal of Computational Geometry (2020). 11(1) 433–475.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
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.

@article{cflrvw-dgflf-JoCG20, abstract = {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.}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, journal = {Journal of Computational Geometry}, keywords = {non-planar_graphs}, number = 1, pages = {433–475}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 11, year = 2020 }
Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes in Computational Geometry: Theory and Applications (2019). 84 50–68.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is \emph{1-planar if every edge is crossed at most once. A 1-planar drawing is \emph{IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is \emph{NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (\emph{beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to \emph{right-angle crossing (\emph{RAC}) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every $$n$$-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size $$O(n) times O(n)$$. Then, we show that every $$n$$-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size $$O(n^3) times O(n^3)$$. Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.

@article{clwz-cd1pg-CGTA19, abstract = {We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is \emph{1-planar} if every edge is crossed at most once. A 1-planar drawing is \emph{IC-planar} if no two pairs of crossing edges share a vertex. A 1-planar drawing is \emph{NIC-planar} if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (\emph{beyond-planar graphs} is a collective term for the primary attempts to generalize the planar graphs) to \emph{right-angle crossing} (\emph{RAC}) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every $n$-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size $O(n) \times O(n)$. Then, we show that every $n$-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size $O(n^3) \times O(n^3)$. Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.}, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, journal = {Computational Geometry: Theory and Applications}, keywords = {myown}, note = {Special Issue on the 34th European Workshop on Computational Geometry}, pages = {50–68}, title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends}, volume = 84, year = 2019 }
Drawing Graphs on Few Circles and Few Spheres Kryven, Myroslav; Ravsky, Alexander; Wolff, Alexander in Journal of Graph Algorithms & Applications (2019). 23(2) 371–391.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
Given a drawing of a graph, its \emph{visual complexity is defined as the number of geometrical entities in the drawing, for example, the number of segments in a straight-line drawing or the number of arcs in a circular-arc drawing (in 2D). Recently, Chaplick et al. [GD 2016] introduced a different measure for the visual complexity, the \emph{affine cover number, which is the minimum number of lines (or planes) that together cover a crossing-free straight-line drawing of a graph G in 2D (3D). In this paper, we introduce the \emph{spherical cover number, which is the minimum number of circles (or spheres) that together cover a crossing-free circular-arc drawing in 2D (or 3D). It turns out that spherical covers are sometimes significantly smaller than affine covers. For complete, complete bipartite, and platonic graphs, we analyze their spherical cover numbers and compare them to their affine cover numbers as well as their segment and arc numbers. We also link the spherical cover number to other graph parameters such as treewidth and linear arboricity.

@article{krw-dgfcf-JGAA19, abstract = {Given a drawing of a graph, its \emph{visual complexity} is defined as the number of geometrical entities in the drawing, for example, the number of segments in a straight-line drawing or the number of arcs in a circular-arc drawing (in 2D). Recently, Chaplick et al.\ [GD 2016] introduced a different measure for the visual complexity, the \emph{affine cover number}, which is the minimum number of lines (or planes) that together cover a crossing-free straight-line drawing of a graph G in 2D (3D). In this paper, we introduce the \emph{spherical cover number}, which is the minimum number of circles (or spheres) that together cover a crossing-free circular-arc drawing in 2D (or 3D). It turns out that spherical covers are sometimes significantly smaller than affine covers. For complete, complete bipartite, and platonic graphs, we analyze their spherical cover numbers and compare them to their affine cover numbers as well as their segment and arc numbers. We also link the spherical cover number to other graph parameters such as treewidth and linear arboricity.}, author = {Kryven, Myroslav and Ravsky, Alexander and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 2, pages = {371–391}, title = {Drawing Graphs on Few Circles and Few Spheres}, volume = 23, year = 2019 }
Approximating the Generalized Minimum Manhattan Network Problem Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen G.; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Algorithmica (2018). 80(4) 1170–1190.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
We consider the \emph{generalized minimum Manhattan network problem (GMMN). The input to this problem is a set $$R$$ of $$n$$ pairs of terminals, which are points in $$\mathbb{R}^2$$. The goal is to find a minimum-length rectilinear network that connects every pair in $$R$$ by a \emph{Manhattan path, that is, a path of axis-parallel line segments whose total length equals the pair's Manhattan distance. This problem is a natural generalization of the extensively studied \emph{minimum Manhattan network problem (MMN) in which $$R$$ consists of all possible pairs of terminals. Another important special case is the well-known \emph{rectilinear Steiner arborescence problem (RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. par We obtain an $$O(\log n)$$-approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple $$O(\log^{d+1 n)$$- approximation algorithm for the problem in arbitrary fixed dimension~$$d$$. As a corollary, we obtain an exponential improvement upon the previously best $$O(n^\epsilon)$$-ratio for MMN in $$d$$ dimensions [ESA 2011]. En route, we show that an existing $$O(\log n)$$-approximation algorithm for 2D-RSA generalizes to higher dimensions.

@article{dfksvw-agmmnp-Algorithmica18, abstract = {We consider the \emph{generalized minimum Manhattan network problem} (GMMN). The input to this problem is a set $R$ of $n$ pairs of terminals, which are points in $\mathbb{R}^2$. The goal is to find a minimum-length rectilinear network that connects every pair in $R$ by a \emph{Manhattan path}, that is, a path of axis-parallel line segments whose total length equals the pair's Manhattan distance. This problem is a natural generalization of the extensively studied \emph{minimum Manhattan network problem} (MMN) in which $R$ consists of all possible pairs of terminals. Another important special case is the well-known \emph{rectilinear Steiner arborescence problem} (RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. \par We obtain an $O(\log n)$-approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple $O(\log^{d+1} n)$- approximation algorithm for the problem in arbitrary fixed dimension $d$. As a corollary, we obtain an exponential improvement upon the previously best $O(n^\epsilon)$-ratio for MMN in $d$ dimensions [ESA 2011]. En route, we show that an existing $O(\log n)$-approximation algorithm for 2D-RSA generalizes to higher dimensions.}, author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander}, journal = {Algorithmica}, keywords = {myown}, number = 4, pages = {1170–1190}, title = {Approximating the Generalized Minimum {Manhattan} Network Problem}, volume = 80, year = 2018 }
On the Maximum Crossing Number Chimani, Markus; Felsner, Stefan; Kobourov, Stephen; Ueckerdt, Torsten; Valtr, Pavel; Wolff, Alexander in Journal of Graph Algorithms & Applications (2018). 22(1) 67–87.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
Research about crossings is typically about minimization. In this paper, we consider \emph{maximizing the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a \emph{convex straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that admits a non-convex drawing with more crossings than any convex drawing. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case. We also prove that the unweighted topological case is NP-hard.

@article{cfkuvw-mcn-JGAA18, abstract = {Research about crossings is typically about minimization. In this paper, we consider \emph{maximizing} the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a \emph{convex} straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that admits a non-convex drawing with more crossings than any convex drawing. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case. We also prove that the unweighted topological case is NP-hard.}, author = {Chimani, Markus and Felsner, Stefan and Kobourov, Stephen and Ueckerdt, Torsten and Valtr, Pavel and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, note = {Special issue on ``Graph Drawing Beyond Planarity''.}, number = 1, pages = {67–87}, title = {On the Maximum Crossing Number}, volume = 22, year = 2018 }
Block Crossings in Storyline Visualizations van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander in Journal of Graph Algorithms & Applications (2017). 21(5) 873–913.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.

@article{dfflmrsw-bcsv-JGAA17, abstract = {Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.}, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, note = {Conference version received \textbf{best paper award} (track A) at GD'16.}, number = 5, pages = {873–913}, title = {Block Crossings in Storyline Visualizations}, volume = 21, year = 2017 }
Beyond Maximum Independent Set: An Extended Integer Programming Formulation for Point Labeling Haunert, Jan-Henrik; Wolff, Alexander in International Journal of Geo-Information (2017). 6(11) article 342, 20 pages.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
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.

@article{hw-bmise-IJGI17, abstract = {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.}, author = {Haunert, Jan-Henrik and Wolff, Alexander}, journal = {International Journal of Geo-Information}, keywords = {point-feature_label_placement}, number = 11, pages = {article 342, 20 pages}, title = {Beyond Maximum Independent Set: An Extended Integer Programming Formulation for Point Labeling}, volume = 6, year = 2017 }
Progress on Partial Edge Drawings Bruckdorfer, Till; Cornelsen, Sabine; Gutwenger, Carsten; Kaufmann, Michael; Montecchiani, Fabrizio; Nöllenburg, Martin; Wolff, Alexander in Journal of Graph Algorithms & Applications (2017). 21(4) 757–786.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been introduced. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on symmetric partial edge drawings (SPEDs) that require the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction �� of the edge lengths (��-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. par We show that, for a fixed stub--edge length ratio ��, not all graphs have a ��-SHPED. Specifically, we show that $$K_{165}$$ does not have a 1/4-SHPED, while bandwidth-$$k$$ graphs always have a $$\Theta(1/\sqrt{k})$$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem MAXSPED where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem of minimizing the total amount of erased ink.

@article{bcgkmnw-pped-JGAA17, abstract = {Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been introduced. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on symmetric partial edge drawings (SPEDs) that require the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction �� of the edge lengths (��-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. \par We show that, for a fixed stub–edge length ratio ��, not all graphs have a ��-SHPED. Specifically, we show that $K_{165}$ does not have a 1/4-SHPED, while bandwidth-$k$ graphs always have a $\Theta(1/\sqrt{k})$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem MAXSPED where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem of minimizing the total amount of erased ink.}, author = {Bruckdorfer, Till and Cornelsen, Sabine and Gutwenger, Carsten and Kaufmann, Michael and Montecchiani, Fabrizio and N{\"o}llenburg, Martin and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {partial_edge_drawings}, number = 4, pages = {757–786}, title = {Progress on Partial Edge Drawings}, volume = 21, year = 2017 }
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 in Algorithmica (2017). 77(3) 902–920.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
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.

@article{bdfkkpsw-iaabc-Algorithmica17, abstract = {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.}, author = {Bekos, Michael A. and van Dijk, Thomas C. and Fink, Martin and Kindermann, Philipp and Kobourov, Stephen and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, journal = {Algorithmica}, keywords = {myown}, number = 3, pages = {902–920}, title = {Improved Approximation Algorithms for Box Contact Representations}, volume = 77, year = 2017 }
Multi-Sided Boundary Labeling Kindermann, Philipp; Niedermann, Benjamin; Rutter, Ignaz; Schaefer, Marcus; Schulz, André; Wolff, Alexander in Algorithmica (2016). 76(1) 225–258.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
In the \emph{Boundary Labeling problem, we are given a set of $$n$$ points, referred to as \emph{sites, 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 \emph{Multi-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.

@article{knrssw-tsblas-Algorithmica16, abstract = {In the \emph{Boundary Labeling} problem, we are given a set of $n$ points, referred to as \emph{sites}, 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 \emph{Multi-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.}, author = {Kindermann, Philipp and Niedermann, Benjamin and Rutter, Ignaz and Schaefer, Marcus and Schulz, Andr{\'e} and Wolff, Alexander}, journal = {Algorithmica}, keywords = {myown}, number = 1, pages = {225–258}, title = {Multi-Sided Boundary Labeling}, volume = 76, year = 2016 }
Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition Lipp, Fabian; Wolff, Alexander; Zink, Johannes in Algorithms (2016). 9(3) article 53, 17 pages.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only $$O(m+n \log n)$$ time per iteration when laying out a graph with $$n$$ vertices and $$m$$ edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).

@article{lwz-ffdgd-Algorithms16, abstract = {The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only $O(m+n \log n)$ time per iteration when laying out a graph with $n$ vertices and $m$ edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).}, author = {Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, journal = {Algorithms}, keywords = {myown}, number = 3, pages = {article 53, 17 pages}, title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition}, volume = 9, year = 2016 }
Matching Labels and Markers in Historical Maps: An Algorithm with Interactive Postprocessing Budig, Benedikt; Dijk, Thomas C. van; Wolff, Alexander in ACM Transactions on Spatial Algorithms and Systems (2016). 2(4) 13:1–24.
- [ BibTeX ]
- [ DOI ]
@article{bdw-mlmh-TSAS16, author = {Budig, Benedikt and Dijk, Thomas C. van and Wolff, Alexander}, journal = {ACM Transactions on Spatial Algorithms and Systems}, keywords = {vgiscience}, number = 4, pages = {13:1–24}, title = {Matching Labels and Markers in Historical Maps: An Algorithm with Interactive Postprocessing}, volume = 2, year = 2016 }
Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander in Journal of Graph Algorithms & Applications (2016). 20(1) 133–158.
- [ BibTeX ]
- [ DOI ]
@article{bdkw-sdpgr-JGAA16, author = {Bekos, Michael A. and van Dijk, Thomas C. and Kindermann, Philipp and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 1, pages = {133–158}, title = {Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends}, volume = 20, year = 2016 }
Ordering Metro Lines by Block Crossings Fink, Martin; Pupyrev, Sergey; Wolff, Alexander in Journal of Graph Algorithms & Applications (2015). 19(1) 111–153.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
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 \emph{block 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.

@article{fpw-omlbc-JGAA15, abstract = {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 \emph{block 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.}, author = {Fink, Martin and Pupyrev, Sergey and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 1, pages = {111–153}, title = {Ordering Metro Lines by Block Crossings}, volume = 19, year = 2015 }
Approximating Minimum Manhattan Networks in Higher Dimensions Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen; Spoerhase, Joachim; Wolff, Alexander in Algorithmica (2015). 71(1) 36–52.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called \emph{terminals in~$$\mathbb{R}^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.

@article{dgkksw-ammnh-Algorithmica15, abstract = {We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called \emph{terminals} in $\mathbb{R}^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.}, author = {Das, Aparna and Gansner, Emden R. and Kaufmann, Michael and Kobourov, Stephen and Spoerhase, Joachim and Wolff, Alexander}, journal = {Algorithmica}, keywords = {myown}, number = 1, pages = {36–52}, title = {Approximating Minimum {Manhattan} Networks in Higher Dimensions}, volume = 71, year = 2015 }
Universal Point Sets for Drawing Planar Graphs with Circular Arcs Angelini, Patrizio; Eppstein, David; Frati, Fabrizio; Kaufmann, Michael; Lazard, Silvain; Mchedlidze, Tamara; Teillaud, Monique; Wolff, Alexander in Journal of Graph Algorithms & Applications (2014). 18(3) 313–324.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
We prove that there exists a set $$S$$ of $$n$$ points in the plane such that every $$n$$-vertex planar graph $$G$$ admits a planar drawing in which every vertex of $$G$$ is placed on a distinct point of $$S$$ and every edge of $$G$$ is drawn as a circular arc.

@article{aefklmtw-upsdp-JGAA14, abstract = {We prove that there exists a set $S$ of $n$ points in the plane such that every $n$-vertex planar graph $G$ admits a planar drawing in which every vertex of $G$ is placed on a distinct point of $S$ and every edge of $G$ is drawn as a circular arc.}, author = {Angelini, Patrizio and Eppstein, David and Frati, Fabrizio and Kaufmann, Michael and Lazard, Silvain and Mchedlidze, Tamara and Teillaud, Monique and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {universal_point_sets}, number = 3, pages = {313–324}, title = {Universal Point Sets for Drawing Planar Graphs with Circular Arcs}, volume = 18, year = 2014 }
Guest Editors’ Foreword (Special Issue of Selected Papers from the 21st Int. Symp. Graph Drawing) Wismath, Stephen; Wolff, Alexander in Journal of Graph Algorithms & Applications (2014). 18(2) 174–175.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@article{ww-gef-JGAA14, author = {Wismath, Stephen and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 2, pages = {174–175}, title = {{Guest Editors' Foreword (Special Issue of Selected Papers from the 21st Int. Symp. Graph Drawing)}}, volume = 18, year = 2014 }
Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation Fink, Martin; Haunert, Jan-Henrik; Spoerhase, Joachim; Wolff, Alexander in IEEE Transactions on Visualization and Computer Graphics (2013). 19(12) 2326–2335.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@article{fhsw-sarsp-InfoVis13, author = {Fink, Martin and Haunert, Jan-Henrik and Spoerhase, Joachim and Wolff, Alexander}, journal = {IEEE Transactions on Visualization and Computer Graphics}, keywords = {myown}, number = 12, pages = {2326–2335}, title = {Selecting the Aspect Ratio of a Scatter Plot Based on Its {Delaunay} Triangulation}, volume = 19, year = 2013 }
Augmenting the Connectivity of Planar and Geometric Graphs Rutter, Ignaz; Wolff, Alexander in Journal of Graph Algorithms & Applications (2012). 16(2) 599–628.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
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.

@article{rw-acpgg-12, abstract = {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.}, author = {Rutter, Ignaz and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 2, pages = {599–628}, title = {Augmenting the Connectivity of Planar and Geometric Graphs}, volume = 16, year = 2012 }
Algorithms for Labeling Focus Regions Fink, Martin; Haunert, Jan-Henrik; Schulz, André; Spoerhase, Joachim; Wolff, Alexander in IEEE Transactions on Visualization and Computer Graphics (2012). 18(12) 2583–2592.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ video ]
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.

@article{fhssw-alfr-InfoVis12, abstract = {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\'ezier 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.}, author = {Fink, Martin and Haunert, Jan-Henrik and Schulz, Andr{\'e} and Spoerhase, Joachim and Wolff, Alexander}, journal = {IEEE Transactions on Visualization and Computer Graphics}, keywords = {myown}, number = 12, pages = {2583–2592}, title = {Algorithms for Labeling Focus Regions}, volume = 18, year = 2012 }
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 in Journal of Computational Geometry (2012). 3(1)
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{accgghmmnprvvw-ccg-12, abstract = {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.}, author = {Atienza, Nieves and de Castro, Natalia and Cort\'{e}s, Carmen and Garrido, M. {\'A}ngeles and Grima, Clara I. and Hern\'{a}ndez, Gregorio and M\'{a}rquez, Alberto and Moreno-Gonz{\'a}lez, Auxiliadora and N\"{o}llenburg, Martin and Portillo, Jos{\'e} Ramon and Reyes, Pedro and Valenzuela, Jes\'{u}s and Villar, Maria Trinidad and Wolff, Alexander}, journal = {Journal of Computational Geometry}, keywords = {realizability}, number = 1, title = {Cover Contact Graphs}, volume = 3, year = 2012 }
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 Algorithmica (2012). 62(1--2) 309–332.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
A \emph{binary tanglegram is a drawing of a pair \ttree{S,T of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. par We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an $$O(n^3)$$-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of \textsc{MaxCut for which the algorithm of Goemans and Williamson yields a $$0.878$$-approximation.

@article{bbbnosw-dcbth-12, abstract = {A \emph{binary tanglegram} is a drawing of a pair \ttree{S,T} of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. \par We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an $O(n^3)$-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of \textsc{MaxCut} for which the algorithm of Goemans and Williamson yields a $0.878$-approximation.}, author = {Buchin, Kevin and Buchin, Maike and Byrka, Jaroslaw and N\"ollenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo I. and Wolff, Alexander}, journal = {Algorithmica}, keywords = {myown}, number = {1–2}, pages = {309–332}, title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability}, volume = 62, year = 2012 }
Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming Nöllenburg, Martin; Wolff, Alexander in IEEE Transactions on Visualization and Computer Graphics (2011). 17(5) 626–641.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{nw-dlhqm-TVCG11, abstract = {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.}, author = {N{\"o}llenburg, Martin and Wolff, Alexander}, journal = {IEEE Transactions on Visualization and Computer Graphics}, keywords = {octilinear_layout}, number = 5, pages = {626–641}, title = {Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming}, volume = 17, year = 2011 }
Optimizing Active Ranges for Consistent Dynamic Map Labeling Been, Ken; Nöllenburg, Martin; Poon, Sheung-Hung; Wolff, Alexander in Computational Geometry: Theory and Applications (2010). 43(3) 312–328.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning---an application with increasing practical importance. In \emph{consistent dynamic map labeling, distracting behavior such as popping and jumping is avoided. We use a model for consistent dynamic labeling in which a label is represented by a 3d-solid, with scale as the third dimension. Each solid can be truncated to a single scale interval, called its \emph{active range, corresponding to the scales at which the label will be selected. The \emph{active range optimization (ARO) problem is to select active ranges so that no two truncated solids intersect and the sum of the heights of the active ranges is maximized. \emph{Simple ARO is a variant in which the active ranges are restricted so that a label is never deselected when zooming in. We investigate both the general and simple variants, for 1d- as well as 2d-maps. par Different label shapes define different ARO variants. We show that 2d-ARO and general 1d-ARO are NP-complete, even for quite simple shapes. We solve simple 1d-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants.

@article{bnpw-oarcd-10, abstract = {Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning—an application with increasing practical importance. In \emph{consistent} dynamic map labeling, distracting behavior such as popping and jumping is avoided. We use a model for consistent dynamic labeling in which a label is represented by a 3d-solid, with scale as the third dimension. Each solid can be truncated to a single scale interval, called its \emph{active range}, corresponding to the scales at which the label will be selected. The \emph{active range optimization (ARO)} problem is to select active ranges so that no two truncated solids intersect and the sum of the heights of the active ranges is maximized. \emph{Simple} ARO is a variant in which the active ranges are restricted so that a label is never deselected when zooming in. We investigate both the general and simple variants, for 1d- as well as 2d-maps. \par Different label shapes define different ARO variants. We show that 2d-ARO and general 1d-ARO are NP-complete, even for quite simple shapes. We solve simple 1d-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants.}, author = {Been, Ken and N{\"o}llenburg, Martin and Poon, Sheung-Hung and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {myown}, number = 3, pages = {312–328}, title = {Optimizing Active Ranges for Consistent Dynamic Map Labeling}, volume = 43, year = 2010 }
Trimming of Graphs, with Application to Point Labeling Erlebach, Thomas; Hagerup, Torben; Jansen, Klaus; Minzlaff, Moritz; Wolff, Alexander in Theory of Computing Systems (2010). 47(3) 613–636.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
For $$t>0$$ and $$g\ge 0$$, a vertex-weighted graph of total weight $$W$$ is \emph{$$(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 \emph{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.

@article{ehjmw-tgapl-10, abstract = {For $t>0$ and $g\ge 0$, a vertex-weighted graph of total weight $W$ is \emph{$(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 \emph{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.}, author = {Erlebach, Thomas and Hagerup, Torben and Jansen, Klaus and Minzlaff, Moritz and Wolff, Alexander}, journal = {Theory of Computing Systems}, keywords = {trimming_weighted_graphs}, number = 3, pages = {613–636}, title = {Trimming of Graphs, with Application to Point Labeling}, volume = 47, year = 2010 }
Area aggregation in map generalisation by mixed-integer programming Haunert, Jan-Henrik; Wolff, Alexander in International Journal of Geographical Information Science (2010). 24(12) 1871–1897.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{hw-aamgm-IJGIS10, abstract = {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.}, author = {Haunert, Jan-Henrik and Wolff, Alexander}, journal = {International Journal of Geographical Information Science}, keywords = {myown}, number = 12, pages = {1871–1897}, title = {Area aggregation in map generalisation by mixed-integer programming}, volume = 24, year = 2010 }
Computing Large Matchings Fast Rutter, Ignaz; Wolff, Alexander in ACM Transactions on Algorithms (2010). 7(1) article 1, 21 pages.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
- [ DOI ]
- [ pdf ]
- [ slides ]
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(\sqrt{n}m)$$ 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 \emph{maximum matchings in slightly superlinear time.

@article{rw-clmf-TALG10, abstract = {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(\sqrt{n}m)$ 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 \emph{maximum} matchings in slightly superlinear time.}, author = {Rutter, Ignaz and Wolff, Alexander}, journal = {ACM Transactions on Algorithms}, keywords = {myown}, number = 1, pages = {article 1, 21 pages}, title = {Computing Large Matchings Fast}, volume = 7, year = 2010 }
Untangling a Planar Graph Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander in Discrete & Computational Geometry (2009). 42(4) 542–569.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
A straight-line drawing $$\delta$$ of a planar graph $$G$$ need not be plane, but can be made so by \emph{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 \textsc{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 $$\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 $$\sqrt{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) \le \sqrt{n-2}+1$$ and an $$n$$-vertex outerplanar graph $$H$$ and a drawing $$\delta_H$$ of $$H$$ with fix$$(H,\delta_H) \le 2 \sqrt{n-1}+1$$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.

@article{gkossw-upg-DCG09, abstract = {A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by \emph{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 \textsc{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 $\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 $\sqrt{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) \le \sqrt{n-2}+1$ and an $n$-vertex outerplanar graph $H$ and a drawing $\delta_H$ of $H$ with fix$(H,\delta_H) \le 2 \sqrt{n-1}+1$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.}, author = {Goaoc, Xavier and Kratochv{\'i}l, Jan and Okamoto, Yoshio and Shin, Chan-Su and Spillner, Andreas and Wolff, Alexander}, journal = {Discrete \& Computational Geometry}, keywords = {untangling}, number = 4, pages = {542–569}, title = {Untangling a Planar Graph}, volume = 42, year = 2009 }
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 International Journal of Foundations of Computer Science (2009). 20(1) 3–23.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
For two points $$p$$ and $$q$$ in the plane, a straight line~$$h$$, called a highway, and a real $$v>1$$, we define the \emph{travel time (also known as the \emph{city distance}) from $$p$$ and $$q$$ to be the time needed to traverse a quickest path from $$p$$ to $$q$$, where the distance is measured with speed $$v$$ on $$h$$ and with speed $$1$$ in the underlying metric elsewhere. par Given a set $$S$$ of $$n$$ points in the plane and a highway speed $$v$$, we consider the problem of finding a \emph{highway that minimizes the maximum travel time over all pairs of points in $$S$$. If the orientation of the highway is fixed, the optimal highway can be computed in linear time, both for the $$L_1$$- and the Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal highway can be computed in $$O(n^2 \log n)$$ time. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.

@article{aaabbcknsw-coh-09, abstract = {For two points $p$ and $q$ in the plane, a straight line $h$, called a highway, and a real $v>1$, we define the \emph{travel time} (also known as the \emph{city distance}) from $p$ and $q$ to be the time needed to traverse a quickest path from $p$ to $q$, where the distance is measured with speed $v$ on $h$ and with speed $1$ in the underlying metric elsewhere. \par Given a set $S$ of $n$ points in the plane and a highway speed $v$, we consider the problem of finding a \emph{highway} that minimizes the maximum travel time over all pairs of points in $S$. If the orientation of the highway is fixed, the optimal highway can be computed in linear time, both for the $L_1$- and the Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal highway can be computed in $O(n^{2} \log n)$ time. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.}, author = {Ahn, Hee-Kap and Alt, Helmut and Asano, Tetsuo and Bae, Sang Won and Brass, Peter and Cheong, Otfried and Knauer, Christian and Na, Hyeon-Suk and Shin, Chan-Su and Wolff, Alexander}, journal = {International Journal of Foundations of Computer Science}, keywords = {time_metric}, number = 1, pages = {3–23}, title = {Constructing Optimal Highways}, volume = 20, year = 2009 }
Matching Points with Rectangles and Squares Bereg, Sergey; Mutsanas, Nikolaus; Wolff, Alexander in Computational Geometry: Theory and Applications (2009). 42(2) 93–108.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
In this paper we deal with the following natural family of geometric matching problems. Given a class $$\cal C$$ of geometric objects and a set $$P$$ of points in the plane, a $$\cal C$$-matching is a set $$M \subseteq \cal C$$ such that every $$C \in M$$ contains exactly two elements of $$P$$. The matching is \emph{perfect if it covers every point, and \emph{strong if the objects do not intersect. We concentrate on matching points using axes-aligned squares and rectangles. We propose an algorithm for strong rectangle matching that, given a set of $$n$$ points, matches at least $$2\lfloor n/3 \rfloor$$ of them, which is worst-case optimal. If we are given a combinatorial matching of the points, we can test efficiently whether it has a realization as a (strong) square matching. The algorithm behind this test can be modified to solve an interesting new point-labeling problem. On the other hand we show that it is NP-hard to decide whether a point set has a perfect strong square matching.

@article{bmw-mprs-09, abstract = {In this paper we deal with the following natural family of geometric matching problems. Given a class $\cal C$ of geometric objects and a set $P$ of points in the plane, a $\cal C$-matching is a set $M \subseteq \cal C$ such that every $C \in M$ contains exactly two elements of $P$. The matching is \emph{perfect} if it covers every point, and \emph{strong} if the objects do not intersect. We concentrate on matching points using axes-aligned squares and rectangles. We propose an algorithm for strong rectangle matching that, given a set of $n$ points, matches at least $2\lfloor n/3 \rfloor$ of them, which is worst-case optimal. If we are given a combinatorial matching of the points, we can test efficiently whether it has a realization as a (strong) square matching. The algorithm behind this test can be modified to solve an interesting new point-labeling problem. On the other hand we show that it is NP-hard to decide whether a point set has a perfect strong square matching.}, author = {Bereg, Sergey and Mutsanas, Nikolaus and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {weak_and_strong_matching}, number = 2, pages = {93–108}, title = {Matching Points with Rectangles and Squares}, volume = 42, year = 2009 }
A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem Benkert, Marc; Gudmundsson, Joachim; Knauer, Christian; van Oostrum, René; Wolff, Alexander in International Journal of Computational Geometry and Applications (2009). 19(3) 267–288.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
We consider the following packing problem. Let $$\alpha$$ be a fixed real in $$(0,1]$$. We are given a bounding rectangle $$\rho$$ and a set $$\cal R$$ of $$n$$ possibly intersecting unit disks whose centers lie in~$$\rho$$. The task is to pack a set $$\cal B$$ of $$m$$ disjoint disks of radius $$\alpha$$ into $$\rho$$ such that no disk in $$\cal B$$ intersects a disk in $$\cal R$$, where $$m$$ is the maximum number of \emph{unit disks that can be packed. In this paper we present a polynomial-time algorithm for $$\alpha = 2/3$$. So far only the case of packing squares has been considered. For that case Baur and Fekete have given a polynomial-time algorithm for $$\alpha=2/3$$ and have shown that the problem cannot be solved in polynomial time for any $$\alpha > 13/14$$ unless $$\cal P=\cal NP}$$.

@article{bgkow-ptaag-09, abstract = {We consider the following packing problem. Let $\alpha$ be a fixed real in $(0,1]$. We are given a bounding rectangle $\rho$ and a set $\cal R$ of $n$ possibly intersecting unit disks whose centers lie in $\rho$. The task is to pack a set $\cal B$ of $m$ disjoint disks of radius $\alpha$ into $\rho$ such that no disk in $\cal B$ intersects a disk in $\cal R$, where $m$ is the maximum number of \emph{unit} disks that can be packed. In this paper we present a polynomial-time algorithm for $\alpha = 2/3$. So far only the case of packing squares has been considered. For that case Baur and Fekete have given a polynomial-time algorithm for $\alpha=2/3$ and have shown that the problem cannot be solved in polynomial time for any $\alpha > 13/14$ unless ${\cal P}={\cal NP}$.}, author = {Benkert, Marc and Gudmundsson, Joachim and Knauer, Christian and van Oostrum, Ren{\'e} and Wolff, Alexander}, journal = {International Journal of Computational Geometry and Applications}, keywords = {myown}, number = 3, pages = {267–288}, title = {A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem}, volume = 19, year = 2009 }
Morphing Polylines: A Step Towards Continuous Generalization Nöllenburg, Martin; Merrick, Damian; Wolff, Alexander; Benkert, Marc in Computers, Environment and Urban Systems (2008). 32(4) 248–260.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{nmwb-mpstc-CEUS08, abstract = {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.}, author = {N{\"o}llenburg, Martin and Merrick, Damian and Wolff, Alexander and Benkert, Marc}, journal = {Computers, Environment and Urban Systems}, keywords = {myown}, number = 4, pages = {248–260}, title = {Morphing Polylines: A Step Towards Continuous Generalization}, volume = 32, year = 2008 }
Delineating Boundaries for Imprecise Regions Reinbacher, Iris; Benkert, Marc; van Kreveld, Marc; Mitchell, Joseph S.B.; Snoeyink, Jack; Wolff, Alexander in Algorithmica (2008). 50(3) 386–414.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
In geographic information retrieval, queries often utilize names of geographic regions that do not have a well-defined boundary, such as ``Southern France.'' We provide two classes of algorithms for the problem of computing reasonable boundaries of such regions, based on evidence of given data points that are deemed likely to lie either inside or outside the region. Our problem formulation leads to a number of problems related to red-blue point separation and minimum-perimeter polygons, many of which we solve algorithmically. We give experimental results from our implementation and a comparison of the two approaches.

@article{rbkmsw-dbir-08, abstract = {In geographic information retrieval, queries often utilize names of geographic regions that do not have a well-defined boundary, such as ``Southern France.'' We provide two classes of algorithms for the problem of computing reasonable boundaries of such regions, based on evidence of given data points that are deemed likely to lie either inside or outside the region. Our problem formulation leads to a number of problems related to red-blue point separation and minimum-perimeter polygons, many of which we solve algorithmically. We give experimental results from our implementation and a comparison of the two approaches.}, author = {Reinbacher, Iris and Benkert, Marc and van Kreveld, Marc and Mitchell, Joseph S.B. and Snoeyink, Jack and Wolff, Alexander}, journal = {Algorithmica}, keywords = {red-blue_separation}, number = 3, pages = {386–414}, title = {Delineating Boundaries for Imprecise Regions}, volume = 50, year = 2008 }
Constructing Interference-Minimal Networks Benkert, Marc; Gudmundsson, Joachim; Haverkort, Herman; Wolff, Alexander in Computational Geometry: Theory and Applications (2008). 40(3) 179–194.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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 \emph{interference 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.

@article{bghw-cimn-08, abstract = {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 \emph{interference} 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.}, author = {Benkert, Marc and Gudmundsson, Joachim and Haverkort, Herman and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {wireless_ad-hoc_networks}, number = 3, pages = {179–194}, title = {Constructing Interference-Minimal Networks}, volume = 40, year = 2008 }
Constructing the City Voronoi Diagram Faster Görke, Robert; Shin, Chan-Su; Wolff, Alexander in International Journal of Computational Geometry and Applications (2008). 18(4) 275–294.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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(\sqrt{n} \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.

@article{gsw-ccvdf-IJCGA08, abstract = {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(\sqrt{n} \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.}, author = {G{\"o}rke, Robert and Shin, Chan-Su and Wolff, Alexander}, journal = {International Journal of Computational Geometry and Applications}, keywords = {wavefront_expansion}, number = 4, pages = {275–294}, title = {Constructing the City {Voronoi} Diagram Faster}, volume = 18, year = 2008 }
Decomposing a Simple Polygon into Pseudo-Triangles and Convex Polygons Gerdjikov, Stefan; Wolff, Alexander in Computational Geometry: Theory and Applications (2008). 41(1--2) 21–30.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition \emph{PT-convex. We are interested in \emph{minimum decompositions, i.e., in decomposing the input polygon into the least number of subpolygons. Allowing subpolygons of one of two types has the potential to reduce the complexity of the resulting decomposition considerably. The problem of decomposing a simple polygon into the least number of \emph{convex polygons has been considered. We extend a dynamic-programming algorithm of Keil and Snoeyink for that problem to the case that both convex polygons and pseudo-triangles are allowed. Our algorithm determines such a decomposition in $$O(n^3)$$ time and space, where $$n$$ is the number of the vertices of the polygon.

@article{gw-dsppt-CGTA08, abstract = {In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition \emph{PT-convex}. We are interested in \emph{minimum} decompositions, i.e., in decomposing the input polygon into the least number of subpolygons. Allowing subpolygons of one of two types has the potential to reduce the complexity of the resulting decomposition considerably. The problem of decomposing a simple polygon into the least number of \emph{convex} polygons has been considered. We extend a dynamic-programming algorithm of Keil and Snoeyink for that problem to the case that both convex polygons and pseudo-triangles are allowed. Our algorithm determines such a decomposition in $O(n^3)$ time and space, where $n$ is the number of the vertices of the polygon.}, author = {Gerdjikov, Stefan and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {simple_polygon}, number = {1–2}, pages = {21–30}, title = {Decomposing a Simple Polygon into Pseudo-Triangles and Convex Polygons}, volume = 41, year = 2008 }
Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps Bekos, Michael A.; Kaufmann, Michael; Symvonis, Antonios; Wolff, Alexander in Computational Geometry: Theory and Applications (2007). 36(3) 215–236.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
In this paper, we present \emph{boundary labeling, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the point sites. Then, we connect each label to its site such that no two connections, so-called \emph{leaders, intersect. Such an approach is common e.g. in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem. par We consider attaching labels to one, two or all four sides of the rectangle. We investigate rectilinear and straight-line leaders. We present simple and efficient algorithms that minimize the total length of the leaders or, in the case of rectilinear leaders, the total number of bends.

@article{bksw-blmea-07, abstract = {In this paper, we present \emph{boundary labeling}, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the point sites. Then, we connect each label to its site such that no two connections, so-called \emph{leaders}, intersect. Such an approach is common e.g.\ in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem. \par We consider attaching labels to one, two or all four sides of the rectangle. We investigate rectilinear and straight-line leaders. We present simple and efficient algorithms that minimize the total length of the leaders or, in the case of rectilinear leaders, the total number of bends.}, author = {Bekos, Michael A. and Kaufmann, Michael and Symvonis, Antonios and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {straight-line_leaders}, number = 3, pages = {215–236}, title = {Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps}, volume = 36, year = 2007 }
Configurations with Few Crossings in Topological Graphs Knauer, Christian; Schramm, Étienne; Spillner, Andreas; Wolff, Alexander in Computational Geometry: Theory and Applications (2007). 37(2) 104–114.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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$$. par We then give a simple fixed-parameter algorithm that tests in $$O^\star(2^k)$$ time whether $$G$$ has a non-crossing configuration for any of the above, where the $$O^\star$$-notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are $$O^\star(1.9999992^k)$$ for spanning trees and $$O^\star((\sqrt{3})^k)$$ for $$s$$-$$t$$ paths and cycles. For spanning trees we also have an $$O^\star(1.968^k)$$-time Monte-Carlo algorithm. Each $$O^\star(\beta^k)$$-time decision algorithms can be turned into an $$O^\star((\beta+1)^k)$$-time optimization algorithm that computes a configuration with the minimum number of crossings.

@article{kssw-cfctg-07, abstract = {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$. \par We then give a simple fixed-parameter algorithm that tests in $O^\star(2^k)$ time whether $G$ has a non-crossing configuration for any of the above, where the $O^\star$-notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are $O^\star(1.9999992^k)$ for spanning trees and $O^\star((\sqrt{3})^k)$ for $s$-$t$ paths and cycles. For spanning trees we also have an $O^\star(1.968^k)$-time Monte-Carlo algorithm. Each $O^\star(\beta^k)$-time decision algorithms can be turned into an $O^\star((\beta+1)^k)$-time optimization algorithm that computes a configuration with the minimum number of crossings.}, author = {Knauer, Christian and Schramm, {\'E}tienne and Spillner, Andreas and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {topological_graphs}, number = 2, pages = {104–114}, title = {Configurations with Few Crossings in Topological Graphs}, volume = 37, year = 2007 }
Drawing Subway Maps: A Survey Wolff, Alexander in Informatik~-- Forschung & Entwicklung (2007). 22(1) 23–44.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
This paper deals with automating the drawing of subway maps. There are two features of schematic subway maps that make them different from drawings of other networks such as flow charts or organigrams. First, most schematic subway maps use not only horizontal and vertical lines, but also diagonals. This gives more flexibility in the layout process, but it also makes the problem provably hard. Second, a subway map represents a network whose components have geographic locations that are roughly known to the users of such a map. This knowledge must be respected during the search for a clear layout of the network. For the sake of visual clarity the underlying geography may be distorted, but it must not be given up, otherwise map users will be hopelessly confused. In this paper we first give a rather generally accepted list of rules that should be adhered to by a good subway map. Next we survey three recent methods for drawing subway maps, analyze their performance with respect to the above rules, and compare the resulting maps among each other and to official subway maps drawn by graphic designers. We then focus on one of the methods, which is based on mixed-integer linear programming, a widely-used global optimization technique. This method guarantees to find a drawing that fulfills a subset of the above-mentioned rules (if such a drawing exists) and optimizes a weighted sum of costs that correspond to the remaining rules. The method can draw even large subway networks such as the London Underground in an aesthetically pleasing manner, similar to maps made by professional graphic designers. If station labels are included in the optimization process, so far only medium-size networks can be drawn. Finally we give evidence why drawing good subway maps is difficult (even without labels).

@article{w-dsms-07, abstract = {This paper deals with automating the drawing of subway maps. There are two features of schematic subway maps that make them different from drawings of other networks such as flow charts or organigrams. First, most schematic subway maps use not only horizontal and vertical lines, but also diagonals. This gives more flexibility in the layout process, but it also makes the problem provably hard. Second, a subway map represents a network whose components have geographic locations that are roughly known to the users of such a map. This knowledge must be respected during the search for a clear layout of the network. For the sake of visual clarity the underlying geography may be distorted, but it must not be given up, otherwise map users will be hopelessly confused. In this paper we first give a rather generally accepted list of rules that should be adhered to by a good subway map. Next we survey three recent methods for drawing subway maps, analyze their performance with respect to the above rules, and compare the resulting maps among each other and to official subway maps drawn by graphic designers. We then focus on one of the methods, which is based on mixed-integer linear programming, a widely-used global optimization technique. This method guarantees to find a drawing that fulfills a subset of the above-mentioned rules (if such a drawing exists) and optimizes a weighted sum of costs that correspond to the remaining rules. The method can draw even large subway networks such as the London Underground in an aesthetically pleasing manner, similar to maps made by professional graphic designers. If station labels are included in the optimization process, so far only medium-size networks can be drawn. Finally we give evidence why drawing good subway maps is difficult (even without labels).}, author = {Wolff, Alexander}, journal = {Informatik – Forschung \& Entwicklung}, keywords = {subway_map}, number = 1, pages = {23–44}, title = {Drawing Subway Maps: A Survey}, volume = 22, year = 2007 }
Farthest-Point Queries with Geometric and Combinatorial Constraints Daescu, Ovidiu; Mi, Ningfang; Shin, Chan-Su; Wolff, Alexander in Computational Geometry: Theory and Applications (2006). 33(3) 174–185.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{dmsw-fpqgc-06, abstract = {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.}, author = {Daescu, Ovidiu and Mi, Ningfang and Shin, Chan-Su and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {polygonal_path_simplification}, number = 3, pages = {174–185}, title = {Farthest-Point Queries with Geometric and Combinatorial Constraints}, volume = 33, year = 2006 }
The Minimum Manhattan Network Problem: Approximations and Exact Solutions Benkert, Marc; Wolff, Alexander; Widmann, Florian; Shirabe, Takeshi in Computational Geometry: Theory and Applications (2006). 35(3) 188–208.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
Given a set of points in the plane and a constant $$t\ge 1$$, a Euclidean $$t$$-\emph{spanner 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 \emph{Manhattan 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.

@article{bwws-mmnpa-06, abstract = {Given a set of points in the plane and a constant $t\ge 1$, a Euclidean $t$-\emph{spanner} 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 \emph{Manhattan 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.}, author = {Benkert, Marc and Wolff, Alexander and Widmann, Florian and Shirabe, Takeshi}, journal = {Computational Geometry: Theory and Applications}, keywords = {spanner}, number = 3, pages = {188–208}, title = {The Minimum {Manhattan} Network Problem: Approximations and Exact Solutions}, volume = 35, year = 2006 }
Optimal Spanners for Axis-Aligned Rectangles Asano, Tetsuo; de Berg, Mark; Cheong, Otfried; Everett, Hazel; Haverkort, Herman; Katoh, Naoki; Wolff, Alexander in Computational Geometry: Theory and Applications (2005). 30(1) 59–77.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{abcehkw-osaar-05, abstract = {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.}, author = {Asano, Tetsuo and de Berg, Mark and Cheong, Otfried and Everett, Hazel and Haverkort, Herman and Katoh, Naoki and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {myown}, number = 1, pages = {59–77}, title = {Optimal Spanners for Axis-Aligned Rectangles}, volume = 30, year = 2005 }
Facility Location and the Geometric Minimum-Diameter Spanning Tree Gudmundsson, Joachim; Haverkort, Herman; Park, Sang-Min; Shin, Chan-Su; Wolff, Alexander in Computational Geometry: Theory and Applications (2004). 27(1) 87–106.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{ghpsw-flgmd-04, abstract = {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.}, author = {Gudmundsson, Joachim and Haverkort, Herman and Park, Sang-Min and Shin, Chan-Su and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {spanning_tree}, number = 1, pages = {87–106}, title = {Facility Location and the Geometric Minimum-Diameter Spanning Tree}, volume = 27, year = 2004 }
Labeling Points with Weights Poon, Sheung-Hung; Shin, Chan-Su; Strijk, Tycho; Uno, Takeaki; Wolff, Alexander in Algorithmica (2003). 38(2) 341–362.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{pssuw-lpw-Algorithmica03, abstract = {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.}, author = {Poon, Sheung-Hung and Shin, Chan-Su and Strijk, Tycho and Uno, Takeaki and Wolff, Alexander}, journal = {Algorithmica}, keywords = {throughput_maximization}, number = 2, pages = {341–362}, title = {Labeling Points with Weights}, volume = 38, year = 2003 }
A Simple Factor-2/3 Approximation Algorithm for Two-Circle Point Labeling Wolff, Alexander; Thon, Michael; Xu, Yinfeng in International Journal of Computational Geometry and Applications (2002). 12(4) 269–281.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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+\sqrt{33}) \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 \emph{optimally 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.

@article{wtx-sf23a-02, abstract = {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+\sqrt{33}) \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 \emph{optimally} 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.}, author = {Wolff, Alexander and Thon, Michael and Xu, Yinfeng}, journal = {International Journal of Computational Geometry and Applications}, keywords = {myown}, number = 4, pages = {269–281}, title = {A Simple Factor-2/3 Approximation Algorithm for Two-Circle Point Labeling}, volume = 12, year = 2002 }
A Tutorial for Designing Flexible Geometric Algorithms Kapoor, Vikas; Kühl, Dietmar; Wolff, Alexander in Algorithmica (2002). 33(1) 52–70.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{kkw-tdfga-02, abstract = {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.}, author = {Kapoor, Vikas and K{\"u}hl, Dietmar and Wolff, Alexander}, journal = {Algorithmica}, keywords = {sweep-line_algorithm}, number = 1, pages = {52–70}, title = {A Tutorial for Designing Flexible Geometric Algorithms}, volume = 33, year = 2002 }
Towards an Evaluation of Quality for Names Placement Methods van Dijk, Steven; van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander in International Journal of Geographical Information Science (2002). 16(7) 641–661.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{dksw-teqnp-02, abstract = {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.}, author = {van Dijk, Steven and van Kreveld, Marc and Strijk, Tycho and Wolff, Alexander}, journal = {International Journal of Geographical Information Science}, keywords = {quality_assessment}, number = 7, pages = {641–661}, title = {Towards an Evaluation of Quality for Names Placement Methods}, volume = 16, year = 2002 }
Three Rules Suffice for Good Label Placement Wagner, Frank; Wolff, Alexander; Kapoor, Vikas; Strijk, Tycho in Algorithmica (2001). 30(2) 334–349.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{wwks-3rsgl-01, abstract = {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.}, author = {Wagner, Frank and Wolff, Alexander and Kapoor, Vikas and Strijk, Tycho}, journal = {Algorithmica}, keywords = {myown}, number = 2, pages = {334–349}, title = {Three Rules Suffice for Good Label Placement}, volume = 30, year = 2001 }
Labeling Points with Circles Strijk, Tycho; Wolff, Alexander in International Journal of Computational Geometry and Applications (2001). 11(2) 181–195.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{sw-lpc-01, abstract = {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.}, author = {Strijk, Tycho and Wolff, Alexander}, journal = {International Journal of Computational Geometry and Applications}, keywords = {visualization}, number = 2, pages = {181–195}, title = {Labeling Points with Circles}, volume = 11, year = 2001 }
Point Labeling with Sliding Labels van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander in Computational Geometry: Theory and Applications (1999). 13(1) 21–47.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{ksw-plsl-CGTA99, abstract = {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.}, author = {van Kreveld, Marc and Strijk, Tycho and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {point_annotation}, number = 1, pages = {21–47}, title = {Point Labeling with Sliding Labels}, volume = 13, year = 1999 }
A Practical Map Labeling Algorithm Wagner, Frank; Wolff, Alexander in Computational Geometry: Theory and Applications (1997). 7(5--6) 387–404.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
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.

@article{ww-pmla-97, abstract = {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.}, author = {Wagner, Frank and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {packing_problem}, number = {5–6}, pages = {387–404}, title = {A Practical Map Labeling Algorithm}, volume = 7, year = 1997 }

Incollection[ to top ]

Räumliche Analyse durch kombinatorische Optimierung Haunert, Jan-Henrik; Wolff, Alexander in Handbuch der Geodäsie (6 B{ä}nde), W. Freeden, R. Rummel (Hrsg.) (2016). 1–39.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@incollection{hw-rako-HG16, author = {Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Handbuch der Geod{\"a}sie (6 B{\"a}nde)}, editor = {Freeden, Willi and Rummel, Reiner}, keywords = {myown}, pages = {1–39}, publisher = {Springer Berlin Heidelberg}, title = {{R{\"a}umliche Analyse durch kombinatorische Optimierung}}, year = 2016 }
Graph Drawing and Cartography Wolff, Alexander in Handbook of Graph Drawing and Visualization, R. Tamassia (Hrsg.) (2013). 697–736.
- [ BibTeX ]
@incollection{w-gdc-HGDV13, author = {Wolff, Alexander}, booktitle = {Handbook of Graph Drawing and Visualization}, chapter = 23, editor = {Tamassia, Roberto}, keywords = {myown}, pages = {697–736}, publisher = {CRC Press, Boca Raton, FL}, title = {Graph Drawing and Cartography}, year = 2013 }
A Simple and Efficient Algorithm for High-Quality Line Labeling Wolff, Alexander; Knipping, Lars; van Kreveld, Marc; Strijk, Tycho; Agarwal, Pankaj K. in Innovations in GIS VII: GeoComputation, P. M. Atkinson, D. J. Martin (Hrsg.) (2000). 147–159.
- [ BibTeX ]
- [ pdf ]
@incollection{wkksa-seahq-00, author = {Wolff, Alexander and Knipping, Lars and van Kreveld, Marc and Strijk, Tycho and Agarwal, Pankaj K.}, booktitle = {Innovations in GIS VII: GeoComputation}, chapter = 11, editor = {Atkinson, Peter M. and Martin, David J.}, keywords = {myown}, pages = {147–159}, publisher = {Taylor \& Francis}, title = {A Simple and Efficient Algorithm for High-Quality Line Labeling}, year = 2000 }
The Hardness of Approximating Set Cover Wolff, Alexander in Lectures on Proof Verification and Approximation Algorithms, E. W. Mayr, H. J. Prömel, A. Steger (Hrsg.) (1998). (Bd. 1367) 249–262.
- [ BibTeX ]
- [ DOI ]
@incollection{w-hasc-98, author = {Wolff, Alexander}, booktitle = {Lectures on Proof Verification and Approximation Algorithms}, chapter = 10, editor = {Mayr, Ernst W. and Pr{\"o}mel, {Hans J{\"u}rgen} and Steger, Angelika}, keywords = {myown}, pages = {249–262}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science Tutorial}, title = {The Hardness of Approximating Set Cover}, volume = 1367, year = 1998 }

Inproceedings[ to top ]

The Complexity of Finding Tangles Firman, Oksana; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes in Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Lecture Notes in Computer Science, L. Gka}sieniec (Hrsg.) (2023). (Bd. 13878) 3–17.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{ffkrwz-cotf-SOFSEM23, author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 49th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'23)}, editor = {G\k{a}sieniec, Leszek}, keywords = {myown}, pages = {3–17}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {The Complexity of Finding Tangles}, volume = 13878, year = 2023 }
Parameterized Approaches to Orthogonal Compaction Didimo, Walter; Gupta, Siddharth; Kindermann, Philipp; Liotta, Giuseppe; Wolff, Alexander; Zehavi, Meirav in Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Lecture Notes in Computer Science, L. Gka}sieniec (Hrsg.) (2023). (Bd. 13878) 111–128.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{dgklwz-paoc-SOFSEM23, author = {Didimo, Walter and Gupta, Siddharth and Kindermann, Philipp and Liotta, Giuseppe and Wolff, Alexander and Zehavi, Meirav}, booktitle = {Proc. 49th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'23)}, editor = {G\k{a}sieniec, Leszek}, keywords = {myown}, pages = {111–128}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Parameterized Approaches to Orthogonal Compaction}, volume = 13878, year = 2023 }
Morphing Planar Graph Drawings Through 3D Buchin, Kevin; Evans, Will; Frati, Fabrizio; Kostitsyna, Irina; Löffler, Maarten; Ophelders, Tim; Wolff, Alexander in Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Lecture Notes in Computer Science, L. Gka}sieniec (Hrsg.) (2023). (Bd. 13878) 80–95.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{befklow-mpgdt3d-SOFSEM23, author = {Buchin, Kevin and Evans, Will and Frati, Fabrizio and Kostitsyna, Irina and L{\"o}ffler, Maarten and Ophelders, Tim and Wolff, Alexander}, booktitle = {Proc. 49th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'23)}, editor = {G\k{a}sieniec, Leszek}, keywords = {myown}, pages = {80–95}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Morphing Planar Graph Drawings Through {3D}}, volume = 13878, year = 2023 }
Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees Klawitter, Jonathan; Klesen, Felix; Niederer, Moritz; Wolff, Alexander in Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Lecture Notes in Computer Science, L. Gka}sieniec (Hrsg.) (2023). (Bd. 13878) 96–110.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{kknw-vmct-SOFSEM23, author = {Klawitter, Jonathan and Klesen, Felix and Niederer, Moritz and Wolff, Alexander}, booktitle = {Proc. 49th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'23)}, editor = {G\k{a}sieniec, Leszek}, keywords = {myown}, pages = {96–110}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees}, volume = 13878, year = 2023 }
Morphing Rectangular Duals Chaplick, Steven; Kindermann, Philipp; Klawitter, Jonathan; Rutter, Ignaz; Wolff, Alexander in Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD’22), Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (Hrsg.) (2022). (Bd. 13764) 389–403.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{ckkrw-mrd-GD22, author = {Chaplick, Steven and Kindermann, Philipp and Klawitter, Jonathan and Rutter, Ignaz and Wolff, Alexander}, booktitle = {Proc. 30th Int. Symp. Graph Drawing \& Network Vis. (GD'22)}, editor = {Angelini, Patrizio and von Hanxleden, Reinhard}, keywords = {myown}, pages = {389–403}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Morphing Rectangular Duals}, volume = 13764, year = 2022 }
Outside-Obstacle Representations with All Vertices on the Outer Face Firman, Oksana; Kindermann, Philipp; Klawitter, Jonathan; Klemz, Boris; Klesen, Felix; Wolff, Alexander in Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD’22), Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (Hrsg.) (2022). (Bd. 13764) 9 pages.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{fkkkkw-ooravof-GD22, author = {Firman, Oksana and Kindermann, Philipp and Klawitter, Jonathan and Klemz, Boris and Klesen, Felix and Wolff, Alexander}, booktitle = {Proc. 30th Int. Symp. Graph Drawing \& Network Vis. (GD'22)}, editor = {Angelini, Patrizio and von Hanxleden, Reinhard}, keywords = {myown}, pages = {9 pages}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Outside-Obstacle Representations with All Vertices on the Outer Face}, volume = 13764, year = 2022 }
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 Proc. 48th Int. Workshop Graph-Theoretic Concepts Comput. Sci. (WG’22), Lecture Notes in Computer Science, M. Bekos, M. Kaufmann (Hrsg.) (2022). (Bd. 13453) 16 pages.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{gkkkkkwz-snaul-WG22, author = {Goe{\ss}mann, Ina and Klawitter, Jonathan and Klemz, Boris and Klesen, Felix and Kobourov, Stephen G. and Kryven, Myroslav and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 48th Int. Workshop Graph-Theoretic Concepts Comput. Sci. (WG'22)}, editor = {Bekos, Michael and Kaufmann, Michael}, keywords = {visual_complexity}, pages = {16 pages}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs}, volume = 13453, year = 2022 }
The Computational Complexity of the ChordLink Model Kindermann, Philipp; Sauer, Jan; Wolff, Alexander in Proc. 38th Europ. Workshop Comput. Geom. (EuroCG’22), E. Di Giacomo, F. Montecchiani (Hrsg.) (2022). 10:1–7.
- [ BibTeX ]
- [ pdf ]
- [ slides ]
@inproceedings{ksw-cccm-EuroCG22, author = {Kindermann, Philipp and Sauer, Jan and Wolff, Alexander}, booktitle = {Proc. 38th Europ. Workshop Comput. Geom. (EuroCG'22)}, editor = {{Di Giacomo}, Emilio and Montecchiani, Fabrizio}, keywords = {myown}, pages = {10:1–7}, title = {The Computational Complexity of the {ChordLink} Model}, year = 2022 }
Algorithms for Floor Planning with Proximity Requirements Klawitter, Jonathan; Klesen, Felix; Wolff, Alexander in Proc. CAAD Future 2021, CCIS, D. J. Gerber, A. Nahmad, B. Bogosian, E. Pantazis, C. Miltiadis (Hrsg.) (2022). (Bd. 1465) 151–171.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{kkw-afppr-CAADF21, author = {Klawitter, Jonathan and Klesen, Felix and Wolff, Alexander}, booktitle = {Proc. CAAD Future 2021}, editor = {Gerber, David J. and Nahmad, Alicia and Bogosian, Biayna and Pantazis, Evan and Miltiadis, Constantinos}, keywords = {myown}, pages = {151–171}, publisher = {Springer-Verlag}, series = {CCIS}, title = {Algorithms for Floor Planning with Proximity Requirements}, volume = 1465, year = 2022 }
Bounding and Computing Obstacle Numbers of Graphs Balko, Martin; Chaplick, Steven; Gupta, Siddharth; Hoffmann, Michael; Valtr, Pavel; Wolff, Alexander in Proc. 30th Europ. Symp. Algorithms (ESA’22), LIPIcs, S. Chechik, G. Navarro, E. Rotenberg, G. Herman (Hrsg.) (2022). (Bd. 244) 11:1–13.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{bcghvw-bcong-ESA22, author = {Balko, Martin and Chaplick, Steven and Gupta, Siddharth and Hoffmann, Michael and Valtr, Pavel and Wolff, Alexander}, booktitle = {Proc. 30th Europ. Symp. Algorithms (ESA'22)}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, keywords = {myown}, pages = {11:1–13}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Bounding and Computing Obstacle Numbers of Graphs}, volume = 244, year = 2022 }
Coloring Mixed and Directional Interval Graphs Gutowski, Grzegorz; Mittelstädt, Florian; Rutter, Ignaz; Spoerhase, Joachim; Wolff, Alexander; Zink, Johannes in Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD’22), Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (Hrsg.) (2022). (Bd. 13764) 14 pages.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{gmrswz-cmdig-GD22, author = {Gutowski, Grzegorz and Mittelst{\"a}dt, Florian and Rutter, Ignaz and Spoerhase, Joachim and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 30th Int. Symp. Graph Drawing \& Network Vis. (GD'22)}, editor = {Angelini, Patrizio and von Hanxleden, Reinhard}, keywords = {myown}, pages = {14 pages}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Coloring Mixed and Directional Interval Graphs}, volume = 13764, year = 2022 }
Using the Metro-Map Metaphor for Drawing Hypergraphs Frank, Fabian; Kaufmann, Michael; Kobourov, Stephen; Mchedlidze, Tamara; Pupyrev, Sergey; Ueckerdt, Torsten; Wolff, Alexander in Proc. 47th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’21), Lecture Notes in Computer Science, T. Burevs}, R. Dondi, J. Gamper, G. Guerrini, T. Jurdziński, C. Pahl, F. Sikora, P. Wong (Hrsg.) (2021). (Bd. 12607) 361–372.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
@inproceedings{fkkmpuw-ummmdh-SOFSEM21, author = {Frank, Fabian and Kaufmann, Michael and Kobourov, Stephen and Mchedlidze, Tamara and Pupyrev, Sergey and Ueckerdt, Torsten and Wolff, Alexander}, booktitle = {Proc. 47th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'21)}, editor = {Bure\v{s}, Tom{\'a}\v{s} and Dondi, Riccardo and Gamper, Johann and Guerrini, Giovanna and Jurdzi{\'n}ski, Tomasz and Pahl, Claus and Sikora, Florian and Wong, Prudence}, keywords = {myown}, pages = {361–372}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Using the Metro-Map Metaphor for Drawing Hypergraphs}, volume = 12607, year = 2021 }
Layered Drawing of Undirected Graphs with Generalized Port Constraints Walter, Julian; Zink, Johannes; Baumeister, Joachim; Wolff, Alexander in Proc. 28th Int. Symp. Graph Drawing & Network Vis. (GD’20), Lecture Notes in Computer Science, D. Auber, P. Valtr (Hrsg.) (2021). (Bd. 12590) 220–234.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{wzbw-ldugg-GD20, author = {Walter, Julian and Zink, Johannes and Baumeister, Joachim and Wolff, Alexander}, booktitle = {Proc. 28th Int. Symp. Graph Drawing \& Network Vis. (GD'20)}, editor = {Auber, David and Valtr, Pavel}, keywords = {myown}, pages = {220–234}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Layered Drawing of Undirected Graphs with Generalized Port Constraints}, volume = 12590, year = 2021 }
Adjacency Graphs of Polyhedral Surfaces Arseneva, Elena; Kleist, Linda; Klemz, Boris; Löffler, Maarten; Schulz, André; Vogtenhuber, Birgit; Wolff, Alexander in Proc. 37th Annu. Sympos. Comput. Geom. (SoCG’21), LIPIcs, K. Buchin, Éric Colin de Verdière (Hrsg.) (2021). (Bd. 189) 11:1–17.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{akklsvw-dgps-SoCG21, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L{\"o}ffler, Maarten and Schulz, Andr{\'e} and Vogtenhuber, Birgit and Wolff, Alexander}, booktitle = {Proc. 37th Annu. Sympos. Comput. Geom. (SoCG'21)}, editor = {Buchin, Kevin and \'{E}ric {Colin de Verdi{\`e}re}}, keywords = {realizability}, pages = {11:1–17}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Adjacency Graphs of Polyhedral Surfaces}, volume = 189, year = 2021 }
Extending Partial Representations of Rectangular Duals with Given Contact Orientations Chaplick, Steven; Kindermann, Philipp; Klawitter, Jonathan; Rutter, Ignaz; Wolff, Alexander in Proc. 12th International Conference on Algorithms and Complexity (CIAC’21), Lecture Notes in Computer Science, T. Calamoneri, F. Coró (Hrsg.) (2021). (Bd. 12701) 340–353.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
- [ video ]
@inproceedings{ckkrw-eprrd-CIAC21, author = {Chaplick, Steven and Kindermann, Philipp and Klawitter, Jonathan and Rutter, Ignaz and Wolff, Alexander}, booktitle = {Proc. 12th International Conference on Algorithms and Complexity (CIAC'21)}, editor = {Calamoneri, Tiziana and Cor{\'o}, Federico}, keywords = {myown}, pages = {340–353}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Extending Partial Representations of Rectangular Duals with Given Contact Orientations}, volume = 12701, year = 2021 }
Angle Covers: Algorithms and Complexity Evans, William; Gethner, Ellen; Spalding-Jamieson, Jack; Wolff, Alexander in Proc. 14th Int. Workshop Algorithms Comput. (WALCOM’20), Lecture Notes in Computer Science, S. Rahman, K. Sadakane, W.-K. Sung (Hrsg.) (2020). (Bd. 12049) 94–106.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{egsw-acac-WALCOM20, author = {Evans, William and Gethner, Ellen and Spalding-Jamieson, Jack and Wolff, Alexander}, booktitle = {Proc. 14th Int. Workshop Algorithms Comput. (WALCOM'20)}, editor = {Rahman, Sohel and Sadakane, Kunihiko and Sung, Wing-Kin}, keywords = {myown}, pages = {94–106}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Angle Covers: Algorithms and Complexity}, volume = 12049, year = 2020 }
Drawing Graphs with Circular Arcs and Right-Angle Crossings Chaplick, Steven; Förster, Henry; Kryven, Myroslav; Wolff, Alexander in Proc. 17th Scand. Symp. and Workshops on Algorithm Theory (SWAT’20), LIPIcs, S. Albers (Hrsg.) (2020). (Bd. 162) 21:1–14.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{cfkw-dgcar-SWAT20, author = {Chaplick, Steven and F{\"o}rster, Henry and Kryven, Myroslav and Wolff, Alexander}, booktitle = {Proc. 17th Scand. Symp. and Workshops on Algorithm Theory (SWAT'20)}, editor = {Albers, Susanne}, keywords = {right-angle_crossings}, pages = {21:1–14}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Drawing Graphs with Circular Arcs and Right-Angle Crossings}, volume = 162, year = 2020 }
Variants of the Segment Number of a Graph Okamoto, Yoshio; Ravsky, Alexander; Wolff, Alexander in Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (Hrsg.) (2019). (Bd. 11904) 430–443.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{orw-ysng-GD19, author = {Okamoto, Yoshio and Ravsky, Alexander and Wolff, Alexander}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and T{\'o}th, Csaba D.}, keywords = {myown}, pages = {430–443}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Variants of the Segment Number of a Graph}, volume = 11904, year = 2019 }
Line and Plane Cover Numbers Revisited Biedl, Therese; Felsner, Stefan; Meijer, Henk; Wolff, Alexander in Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (Hrsg.) (2019). (Bd. 11904) 409–415.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{bfmw-lpcnr-GD19, author = {Biedl, Therese and Felsner, Stefan and Meijer, Henk and Wolff, Alexander}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and T{\'o}th, Csaba D.}, keywords = {myown}, pages = {409–415}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Line and Plane Cover Numbers Revisited}, volume = 11904, year = 2019 }
Representing Graphs and Hypergraphs by Touching Polygons in 3D Evans, William; Rzka}.zewski, Pawel}; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander in Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (Hrsg.) (2019). (Bd. 11904) 18–32.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
@inproceedings{erssw-rghtp-GD19, author = {Evans, William and Rz\k{a}\.zewski, Pawe\l{} and Saeedi, Noushin and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and T{\'o}th, Csaba D.}, keywords = {myown}, note = {http://arxiv.org/abs/1908.08273}, pages = {18–32}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Representing Graphs and Hypergraphs by Touching Polygons in {3D}}, volume = 11904, year = 2019 }
Bundled Crossings Revisited Chaplick, Steven; van Dijk, Thomas C.; Kryven, Myroslav; Park, Ji-Won; Ravsky, Alexander; Wolff, Alexander in Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (Hrsg.) (2019). (Bd. 11904) 63–77.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{cdkprw-bcr-GD19, author = {Chaplick, Steven and van Dijk, Thomas C. and Kryven, Myroslav and Park, Ji-Won and Ravsky, Alexander and Wolff, Alexander}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and T{\'o}th, Csaba D.}, keywords = {myown}, pages = {63–77}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Bundled Crossings Revisited}, volume = 11904, year = 2019 }
Computing Optimal-Height Tangles Faster Firman, Oksana; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes in Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (Hrsg.) (2019). (Bd. 11904) 203–215.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{fkrwz-cohtf-GD19, author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and T{\'o}th, Csaba D.}, keywords = {myown}, pages = {203–215}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Computing Optimal-Height Tangles Faster}, volume = 11904, year = 2019 }
Stick Graphs with Length Constraints Chaplick, Steven; Kindermann, Philipp; Löffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes in Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (Hrsg.) (2019). (Bd. 11904) 3–17.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{ckltwzz-sglc-GD19, author = {Chaplick, Steven and Kindermann, Philipp and L{\"o}ffler, Andre and Thiele, Florian and Wolff, Alexander and Zaft, Alexander and Zink, Johannes}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and T{\'o}th, Csaba D.}, keywords = {myown}, pages = {3–17}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Stick Graphs with Length Constraints}, volume = 11904, year = 2019 }
On Arrangements of Orthogonal Circles Chaplick, Steven; Förster, Henry; Kryven, Myroslav; Wolff, Alexander in Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (Hrsg.) (2019). (Bd. 11904) 216–229.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{cfkw-aoc-GD19, author = {Chaplick, Steven and F{\"o}rster, Henry and Kryven, Myroslav and Wolff, Alexander}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and T{\'o}th, Csaba D.}, keywords = {myown}, pages = {216–229}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {On Arrangements of Orthogonal Circles}, volume = 11904, year = 2019 }
Beyond Outerplanarity Chaplick, Steven; Kryven, Myroslav; Liotta, Giuseppe; Löffler, Andre; Wolff, Alexander in Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Lecture Notes in Computer Science, F. Frati, K.-L. Ma (Hrsg.) (2018). (Bd. 10692) 546–559.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{ckllw-bo-GD17, author = {Chaplick, Steven and Kryven, Myroslav and Liotta, Giuseppe and L{\"o}ffler, Andre and Wolff, Alexander}, booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, pages = {546–559}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Beyond Outerplanarity}, volume = 10692, year = 2018 }
Drawing Graphs on Few Circles and Few Spheres Kryven, Myroslav; Ravsky, Alexander; Wolff, Alexander in Proc. 4th Conf. Algorithms & Discrete Appl. Math. (CALDAM’18), Lecture Notes in Computer Science, B. S. Panda, P. P. Goswami (Hrsg.) (2018). (Bd. 10743) 164–178.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ poster ]
@inproceedings{krw-dgfcf-CALDAM18, author = {Kryven, Myroslav and Ravsky, Alexander and Wolff, Alexander}, booktitle = {Proc. 4th Conf. Algorithms \& Discrete Appl. Math. (CALDAM'18)}, editor = {Panda, Bhawani S. and Goswami, Partha P.}, keywords = {myown}, note = {Best presentation award for Myroslav Kryven.}, pages = {164–178}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Graphs on Few Circles and Few Spheres}, volume = 10743, year = 2018 }
Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes in Proc. 26th Int. Symp. Graph Drawing & Network Vis. (GD’18), Lecture Notes in Computer Science, T. Biedl, A. Kerren (Hrsg.) (2018). (Bd. 11282) 137–151.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{clwz-cd1pg-GD18, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 26th Int. Symp. Graph Drawing \& Network Vis. (GD'18)}, editor = {Biedl, Therese and Kerren, Andreas}, keywords = {myown}, pages = {137–151}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends}, volume = 11282, year = 2018 }
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 Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Lecture Notes in Computer Science, F. Frati, K.-L. Ma (Hrsg.) (2018). (Bd. 10692) 465–478.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{cccdnptw-plddg-GD17, author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and {Da Lozzo}, Giordano and N{\"o}llenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander}, booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, pages = {465–478}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Planar L-Drawings of Directed Graphs}, volume = 10692, year = 2018 }
Computing Storylines with Few Block Crossings van Dijk, Thomas C.; Lipp, Fabian; Markfelder, Peter; Wolff, Alexander in Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Lecture Notes in Computer Science, F. Frati, K.-L. Ma (Hrsg.) (2018). (Bd. 10692) 365–378.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{dlmw-csfbc-GD17, author = {van Dijk, Thomas C. and Lipp, Fabian and Markfelder, Peter and Wolff, Alexander}, booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, pages = {365–378}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Computing Storylines with Few Block Crossings}, volume = 10692, year = 2018 }
On the Maximum Crossing Number Chimani, Markus; Felsner, Stefan; Kobourov, Stephen; Ueckerdt, Torsten; Valtr, Pavel; Wolff, Alexander in Proc. 28th Int. Workshop Combin. Algorithms (IWOCA’17), Lecture Notes in Computer Science, L. Brankovic, J. Ryan, B. Smith (Hrsg.) (2018). (Bd. 10765) 14 pages.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{cfkuvw-mcn-IWOCA18, author = {Chimani, Markus and Felsner, Stefan and Kobourov, Stephen and Ueckerdt, Torsten and Valtr, Pavel and Wolff, Alexander}, booktitle = {Proc. 28th Int. Workshop Combin. Algorithms (IWOCA'17)}, editor = {Brankovic, Ljiljana and Ryan, Joe and Smith, Bill}, keywords = {myown}, pages = {14 pages}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {On the Maximum Crossing Number}, volume = 10765, year = 2018 }
Stabbing Rectangles by Line Segments~-- How Decomposition Reduces the Shallow-Cell Complexity Chan, Timothy M.; van Dijk, Thomas C.; Fleszar, Krzysztof; Spoerhase, Joachim; Wolff, Alexander in Proc. 29th Annu. Int. Symp. Algorithms Comput. (ISAAC’18), LIPIcs, W.-L. Hsu, D.-T. Lee, C.-S. Liao (Hrsg.) (2018). (Bd. 123) 61:1–13.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{cdfsw-srls-ISAAC18, author = {Chan, Timothy M. and van Dijk, Thomas C. and Fleszar, Krzysztof and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 29th Annu. Int. Symp. Algorithms Comput. (ISAAC'18)}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, keywords = {myown}, pages = {61:1–13}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Stabbing Rectangles by Line Segments – {How} Decomposition Reduces the Shallow-Cell Complexity}, volume = 123, year = 2018 }
Multi-Level Steiner Trees Ahmed, Abu Reyan; Angelini, Patrizio; Darabi Sahneh, Faryad; Efrat, Alon; Glickenstein, David; Gronemann, Martin; Heinsohn, Niklas; Kobourov, Stephen G.; Spence, Richard; Watkins, Joseph; Wolff, Alexander in Proc. 17th Int. Symp. Exper. Algorithms (SEA’18), LIPIcs, G. D’Angelo (Hrsg.) (2018). (Bd. 103) 15:1–14.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{aadegghksww-mlst-SEA18, author = {Ahmed, {Abu Reyan} and Angelini, Patrizio and {Darabi Sahneh}, Faryad and Efrat, Alon and Glickenstein, David and Gronemann, Martin and Heinsohn, Niklas and Kobourov, Stephen G. and Spence, Richard and Watkins, Joseph and Wolff, Alexander}, booktitle = {Proc. 17th Int. Symp. Exper. Algorithms (SEA'18)}, editor = {D'Angelo, Gianlorenzo}, keywords = {myown}, pages = {15:1–14}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Multi-Level Steiner Trees}, volume = 103, year = 2018 }
On the Weak Line Cover Numbers Firman, Oksana; Ravsky, Alexander; Wolff, Alexander in Proc. 34th Europ. Workshop Comput. Geom. (EuroCG’18), M. Korman, W. Mulzer (Hrsg.) (2018). 63:1–5.
- [ BibTeX ]
- [ URL ]
@inproceedings{frw-wlcn-EuroCG18, author = {Firman, Oksana and Ravsky, Alexander and Wolff, Alexander}, booktitle = {Proc. 34th Europ. Workshop Comput. Geom. (EuroCG'18)}, editor = {Korman, Matias and Mulzer, Wolfgang}, keywords = {myown}, pages = {63:1–5}, title = {On the Weak Line Cover Numbers}, year = 2018 }
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 Proc. 26th Int. Symp. Graph Drawing & Network Vis. (GD’18), Lecture Notes in Computer Science, T. Biedl, A. Kerren (Hrsg.) (2018). (Bd. 11282) 509–523.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{acfknorw-osol1-GD18, author = {Argyriou, Evmorfia and Cornelsen, Sabine and F{\"o}rster, Henry and Kaufmann, Michael and N{\"o}llenburg, Martin and Okamoto, Yoshio and Raftopoulou, Chrysanthi and Wolff, Alexander}, booktitle = {Proc. 26th Int. Symp. Graph Drawing \& Network Vis. (GD'18)}, editor = {Biedl, Therese and Kerren, Andreas}, keywords = {myown}, pages = {509–523}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity}, volume = 11282, year = 2018 }
The Complexity of Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Proc. Algorithms Data Struct. Symp. (WADS’17), Lecture Notes in Computer Science, F. Ellen, A. Kolokolova, J.-R. Sack (Hrsg.) (2017). (Bd. 10389) 265–276.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{cflrvw-cdgfl-WADS17, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)}, editor = {Ellen, Faith and Kolokolova, Antonina and Sack, J{\"o}rg-R{\"u}diger}, keywords = {myown}, pages = {265–276}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {The Complexity of Drawing Graphs on Few Lines and Few Planes}, volume = 10389, year = 2017 }
Using the A* Algorithm to Find Optimal Sequences for Area Aggregation Peng, Dongliang; Wolff, Alexander; Haunert, Jan-Henrik in Proc. 28th Int. Cartogr. Conf. (ICC’17) -- Advances in Cartogr. & GIScience, Lect. Notes Geoinform. Cartogr., M. P. Peterson (Hrsg.) (2017). 389–404.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{pwh-uaafo-ICC17, author = {Peng, Dongliang and Wolff, Alexander and Haunert, Jan-Henrik}, booktitle = {Proc. 28th Int. Cartogr. Conf. (ICC'17) – Advances in Cartogr. \& GIScience}, editor = {Peterson, Michael P.}, keywords = {type_change}, pages = {389–404}, publisher = {Springer-Verlag}, series = {Lect. Notes Geoinform. Cartogr.}, title = {Using the {A}* Algorithm to Find Optimal Sequences for Area Aggregation}, year = 2017 }
Algorithmically-Guided User Interaction van Dijk, Thomas C.; Wolff, Alexander in Proc. 25th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’17), E. Hoel, S. D. Newsam, S. Ravada, R. Tamassia, G. Trajcevski (Hrsg.) (2017). 11:1–4.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{dw-agui-ACMGIS17, author = {van Dijk, Thomas C. and Wolff, Alexander}, booktitle = {Proc. 25th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS'17)}, editor = {Hoel, Erik and Newsam, Shawn D. and Ravada, Siva and Tamassia, Roberto and Trajcevski, Goce}, keywords = {myown_vgiscience}, pages = {11:1–4}, title = {Algorithmically-Guided User Interaction}, year = 2017 }
Minimum Rectilinear Polygons for Given Angle Sequences Evans, William S.; Fleszar, Krzysztof; Kindermann, Philipp; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander in Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG’16), Lecture Notes in Computer Science, J. Akiyama, H. Ito, T. Sakai (Hrsg.) (2016). (Bd. 9943) 105–119.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{efkssw-mrpga-JCDCGG16, author = {Evans, William S. and Fleszar, Krzysztof and Kindermann, Philipp and Saeedi, Noushin and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG'16)}, editor = {Akiyama, Jin and Ito, Hiro and Sakai, Toshinori}, keywords = {myown}, pages = {105–119}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Minimum Rectilinear Polygons for Given Angle Sequences}, volume = 9943, year = 2016 }
Obstructing Visibilities with One Obstacle Chaplick, Steven; Lipp, Fabian; Park, Ji-won; Wolff, Alexander in Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (Hrsg.) (2016). (Bd. 9801) 295–308.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{clpw-ov1o-GD16, author = {Chaplick, Steven and Lipp, Fabian and Park, {Ji-won} and Wolff, Alexander}, booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)}, editor = {Hu, Yifan and N{\"o}llenburg, Martin}, keywords = {myown}, pages = {295–308}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Obstructing Visibilities with One Obstacle}, volume = 9801, year = 2016 }
Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (Hrsg.) (2016). (Bd. 9801) 166–180.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{cflrvw-dgflf-GD16, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)}, editor = {Hu, Yifan and N{\"o}llenburg, Martin}, keywords = {myown}, pages = {166–180}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 9801, year = 2016 }
Continuous Generalization of Administrative Boundaries Based on Compatible Triangulations Peng, Dongliang; Wolff, Alexander; Haunert, Jan-Henrik in Proc. 19th AGILE Conference on Geographic Information Science~-- Geospatial Data in a Changing World, Lect. Notes Geoinf. Cartogr., T. Sarjakoski, M. Y. Santos, L. T. Sarjakoski (Hrsg.) (2016). 399–415.
- [ BibTeX ]
- [ DOI ]
@inproceedings{pwh-cgabb-AGILE16, author = {Peng, Dongliang and Wolff, Alexander and Haunert, Jan-Henrik}, booktitle = {Proc. 19th {AGILE} Conference on Geographic Information Science – Geospatial Data in a Changing World}, editor = {Sarjakoski, Tapani and Santos, Maribel Yasmina and Sarjakoski, L. Tiina}, keywords = {myown}, pages = {399–415}, publisher = {Springer-Verlag}, series = {Lect. Notes Geoinf. Cartogr.}, title = {Continuous Generalization of Administrative Boundaries Based on Compatible Triangulations}, year = 2016 }
Block Crossings in Storyline Visualizations van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander in Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (Hrsg.) (2016). (Bd. 9801) 382–398.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{dfflmrsw-bcsv-GD16, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander}, booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)}, editor = {Hu, Yifan and N{\"o}llenburg, Martin}, keywords = {myown}, note = {Received best-paper award at GD 2016}, pages = {382–398}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Block Crossings in Storyline Visualizations}, volume = 9801, year = 2016 }
Beyond Maximum Independent Set: An Extended Model for Point-Feature Label Placement Haunert, Jan-Henrik; Wolff, Alexander in Proc. ISPRS (Commission II, WG II/2) (2016). (Bd. XLI-B2) 109–114.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{hw-bmise-ISPRS16, author = {Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Proc. ISPRS (Commission II, WG II/2)}, keywords = {myown}, pages = {109–114}, title = {Beyond Maximum Independent Set: An Extended Model for Point-Feature Label Placement}, volume = {XLI-B2}, year = 2016 }
Snapping Graph Drawings to the Grid Optimally Löffler, Andre; van Dijk, Thomas C.; Wolff, Alexander in Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (Hrsg.) (2016). (Bd. 9801) 144–151.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{ldw-sgdgo-GD16, author = {L{\"o}ffler, Andre and van Dijk, Thomas C. and Wolff, Alexander}, booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)}, editor = {Hu, Yifan and N{\"o}llenburg, Martin}, keywords = {myown}, pages = {144–151}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Snapping Graph Drawings to the Grid Optimally}, volume = 9801, year = 2016 }
Pixel and Voxel Representations of Graphs Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander in Proc. 23rd Int. Symp. Graph Drawing & Network Vis. (GD’15), Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (Hrsg.) (2015). (Bd. 9411) 472–486.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{abruw-pvrg-GD15, author = {Alam, Md. Jawaherul and Bl{\"a}sius, Thomas and Rutter, Ignaz and Ueckerdt, Torsten and Wolff, Alexander}, booktitle = {Proc. 23rd Int. Symp. Graph Drawing \& Network Vis. (GD'15)}, editor = {{Di Giacomo}, Emilio and Lubiw, Anna}, keywords = {myown}, pages = {472–486}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Pixel and Voxel Representations of Graphs}, volume = 9411, year = 2015 }
Labeling Streets Along a Route in Interactive 3D Maps Using Billboards Schwartges, Nadine; Morgan, Benjamin; Haunert, Jan-Henrik; Wolff, Alexander in Proc. 18th AGILE Conf. Geogr. Inform. Sci. (AGILE’15), Lecture Notes in Geoinformation and Cartography, F. Bacao, M. Y. Santos, M. Painho (Hrsg.) (2015). 269–287.
- [ BibTeX ]
- [ DOI ]
@inproceedings{smhw-lsari-AGILE15, author = {Schwartges, Nadine and Morgan, Benjamin and Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Proc. 18th AGILE Conf. Geogr. Inform. Sci. (AGILE'15)}, editor = {Bacao, Fernando and Santos, Maribel Yasmina and Painho, Marco}, keywords = {myown}, pages = {269–287}, publisher = {Springer-Verlag}, series = {Lecture Notes in Geoinformation and Cartography}, title = {Labeling Streets Along a Route in Interactive 3D Maps Using Billboards}, year = 2015 }
Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition Lipp, Fabian; Wolff, ALexander; Zink, Johannes in Proc. 23rd Int. Symp. Graph Drawing & Network Vis. (GD’15), Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (Hrsg.) (2015). (Bd. 9411) 52–59.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{lwz-ffggd-GD15, author = {Lipp, Fabian and Wolff, ALexander and Zink, Johannes}, booktitle = {Proc. 23rd Int. Symp. Graph Drawing \& Network Vis. (GD'15)}, editor = {{Di Giacomo}, Emilio and Lubiw, Anna}, keywords = {myown}, pages = {52–59}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition}, volume = 9411, year = 2015 }
Solving Optimization Problems on Orthogonal Ray Graphs Chaplick, Steven; Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander in Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG’15) (2015). 2 pp.
- [ BibTeX ]
- [ pdf ]
@inproceedings{cklw-sopor-JCDCGG15, author = {Chaplick, Steven and Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG'15)}, keywords = {myown}, note = {Abstract}, pages = {2 pp.}, title = {Solving Optimization Problems on Orthogonal Ray Graphs}, year = 2015 }
Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander in Proc. 9th Int. Workshop Algorithms Comput. (WALCOM’15), Lecture Notes in Computer Science, M. S. Rahman, E. Tomita (Hrsg.) (2015). (Bd. 8973) 222–233.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ poster ]
@inproceedings{bdkw-sdpgr-WALCOM15, author = {Bekos, Michael A. and van Dijk, Thomas C. and Kindermann, Philipp and Wolff, Alexander}, booktitle = {Proc. 9th Int. Workshop Algorithms Comput. (WALCOM'15)}, editor = {Rahman, M. Sohel and Tomita, Etsuji}, keywords = {myown}, pages = {222–233}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends}, volume = 8973, year = 2015 }
Colored Non-Crossing Euclidean Steiner Forest Bereg, Sergey; Fleszar, Krzysztof; Kindermann, Philipp; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander in Proc. 26th Annu. Int. Symp. Algorithms Comput. (ISAAC’15), Lecture Notes in Computer Science, K. Elbassioni, K. Makino (Hrsg.) (2015). (Bd. 9472) 1–13.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{bfkpsw-cnesf-ISAAC15, author = {Bereg, Sergey and Fleszar, Krzysztof and Kindermann, Philipp and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 26th Annu. Int. Symp. Algorithms Comput. (ISAAC'15)}, editor = {Elbassioni, Khaled and Makino, Kazuhisa}, keywords = {myown}, pages = {1–13}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Colored Non-Crossing {Euclidean} {Steiner} Forest}, volume = 9472, year = 2015 }
Drawing Graphs within Restricted Area Aulbach, Maximilian; Fink, Martin; Schuhmann, Julian; Wolff, Alexander in Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Lecture Notes in Computer Science, C. Duncan, A. Symvonis (Hrsg.) (2014). (Bd. 8871) 367–379.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{afsw-dgra-GD14, author = {Aulbach, Maximilian and Fink, Martin and Schuhmann, Julian and Wolff, Alexander}, booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)}, editor = {Duncan, Christian and Symvonis, Antonios}, keywords = {myown}, pages = {367–379}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Graphs within Restricted Area}, volume = 8871, year = 2014 }
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 in Proc. 22nd Annu. Europ. Symp. Algorithms (ESA’14), Lecture Notes in Computer Science, A. Schulz, D. Wagner (Hrsg.) (2014). (Bd. 8737) 87–99.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{bdfkkpsw-iaabc-ESA14, author = {Bekos, Michael A. and van Dijk, Thomas C. and Fink, Martin and Kindermann, Philipp and Kobourov, Stephen and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 22nd Annu. Europ. Symp. Algorithms (ESA'14)}, editor = {Schulz, Andreas and Wagner, Dorothea}, keywords = {myown}, pages = {87–99}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Improved Approximation Algorithms for Box Contact Representations}, volume = 8737, year = 2014 }
Point Labeling with Sliding Labels in Interactive Maps Schwartges, Nadine; Haunert, Jan-Henrik; Wolff, Alexander; Zwiebler, Dennis in Proc. 17th AGILE Conf. Geogr. Inform. Sci. (AGILE’14), Lecture Notes in Geoinformation and Cartography, J. Huerta, S. Schade, C. Granell (Hrsg.) (2014). 295–310.
- [ BibTeX ]
- [ DOI ]
@inproceedings{shwz-plsli-AGILE14, author = {Schwartges, Nadine and Haunert, Jan-Henrik and Wolff, Alexander and Zwiebler, Dennis}, booktitle = {Proc. 17th AGILE Conf. Geogr. Inform. Sci. (AGILE'14)}, editor = {Huerta, Joaqu{\'i}n and Schade, Sven and Granell, Carlos}, keywords = {myown}, pages = {295–310}, publisher = {Springer-Verlag}, series = {Lecture Notes in Geoinformation and Cartography}, title = {Point Labeling with Sliding Labels in Interactive Maps}, year = 2014 }
Watch Your Data Structures Peng, Dongliang; Wolff, Alexander in Proc. 22th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK’14) (2014). 10 pages.
- [ BibTeX ]
- [ pdf ]
@inproceedings{pw-wyds-GISRUK14, address = {Glasgow}, author = {Peng, Dongliang and Wolff, Alexander}, booktitle = {Proc. 22th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK'14)}, keywords = {myown}, pages = {10 pages}, title = {Watch Your Data Structures}, year = 2014 }
Luatodonotes: Boundary Labeling for Annotations in Texts Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander in Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Lecture Notes in Computer Science, C. Duncan, A. Symvonis (Hrsg.) (2014). (Bd. 8871) 76–88.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{klw-lblat-GD14, author = {Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)}, editor = {Duncan, Christian and Symvonis, Antonios}, keywords = {myown}, pages = {76–88}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Luatodonotes: Boundary Labeling for Annotations in Texts}, volume = 8871, year = 2014 }
Labeling Streets in Interactive Maps using Embedded Labels Schwartges, Nadine; Wolff, Alexander; Haunert, Jan-Henrik in Proc. 22nd ACM SIGSPATIAL Int. Conf. Advances Geogr. Inform. Syst. (ACM-GIS’14), Y. Huang, M. Schneider, M. Gertz, J. Krumm, J. Sankaranarayanan (Hrsg.) (2014). 517–520.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{swh-lsime-ACMGIS14, author = {Schwartges, Nadine and Wolff, Alexander and Haunert, Jan-Henrik}, booktitle = {Proc. 22nd ACM SIGSPATIAL Int. Conf. Advances Geogr. Inform. Syst. (ACM-GIS'14)}, editor = {Huang, Yan and Schneider, Markus and Gertz, Michael and Krumm, John and Sankaranarayanan, Jagan}, keywords = {myown}, pages = {517–520}, title = {Labeling Streets in Interactive Maps using Embedded Labels}, year = 2014 }
Concentric Metro Maps Fink, Martin; Lechner, Magnus; Wolff, Alexander in Proc. Schematic Mapping Workshop (SMW’14) (2014).
- [ BibTeX ]
- [ URL ]
- [ pdf ]
@inproceedings{flw-cmm-SMW14, author = {Fink, Martin and Lechner, Magnus and Wolff, Alexander}, booktitle = {Proc. Schematic Mapping Workshop (SMW'14)}, keywords = {myown}, note = {Poster}, title = {Concentric Metro Maps}, year = 2014 }
Smooth Orthogonal Drawings of Planar Graphs Alam, Md. Jawaherul; Bekos, Michael A.; Kaufmann, Michael; Kindermann, Philipp; Kobourov, Stephen G.; Wolff, Alexander in Proc. 11th Latin American Sympos. Theor. Inform. (LATIN’14), Lecture Notes in Computer Science, A. Pardo, A. Viola (Hrsg.) (2014). (Bd. 8392) 144–155.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{abkkkw-sodpg-LATIN14, author = {Alam, Md. Jawaherul and Bekos, Michael A. and Kaufmann, Michael and Kindermann, Philipp and Kobourov, Stephen G. and Wolff, Alexander}, booktitle = {Proc. 11th Latin American Sympos. Theor. Inform. (LATIN'14)}, editor = {Pardo, Alfredo and Viola, Alfredo}, keywords = {myown}, pages = {144–155}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Smooth Orthogonal Drawings of Planar Graphs}, volume = 8392, year = 2014 }
On Monotone Drawings of Trees Kindermann, Philipp; Schulz, André; Spoerhase, Joachim; Wolff, Alexander in Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Lecture Notes in Computer Science, C. Duncan, A. Symvonis (Hrsg.) (2014). (Bd. 8871) 488–500.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{kssw-mdt-GD14, author = {Kindermann, Philipp and Schulz, Andr{\'e} and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)}, editor = {Duncan, Christian and Symvonis, Antonios}, keywords = {myown}, pages = {488–500}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {On Monotone Drawings of Trees}, volume = 8871, year = 2014 }
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 Proc. 11th Latin American Sympos. Theor. Inform. (LATIN’14), Lecture Notes in Computer Science, A. Pardo, A. Viola (Hrsg.) (2014). (Bd. 8392) 514–525.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{bfklnopsuw-swcrh-LATIN14, author = {Barth, Lukas and Fabrikant, Sara Irina and Kobourov, Stephen and Lubiw, Anna and N{\"o}llenburg, Martin and Okamoto, Yoshio and Pupyrev, Sergey and Squarcella, Claudio and Ueckerdt, Torsten and Wolff, Alexander}, booktitle = {Proc. 11th Latin American Sympos. Theor. Inform. (LATIN'14)}, editor = {Pardo, Alfredo and Viola, Alfredo}, keywords = {myown}, pages = {514–525}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Semantic Word Cloud Representations: Hardness and Approximation Algorithms}, volume = 8392, year = 2014 }
Approximating the Generalized Minimum Manhattan Network Problem Das, Aparna; Fleszar, Krzysztof; Kobourov, Stephen G.; Spoerhase, Joachim; Veeramoni, Sankar; Wolff, Alexander in Proc. 24th Annu. Int. Symp. Algorithms Comput. (ISAAC’13), Lecture Notes in Computer Science, L. Cai, S.-W. Cheng, T.-W. Lam (Hrsg.) (2013). (Bd. 8283) 722–732.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{dfksvw-agmmnp-ISAAC13, author = {Das, Aparna and Fleszar, Krzysztof and Kobourov, Stephen G. and Spoerhase, Joachim and Veeramoni, Sankar and Wolff, Alexander}, booktitle = {Proc. 24th Annu. Int. Symp. Algorithms Comput. (ISAAC'13)}, editor = {Cai, Leizhen and Cheng, Siu-Wing and Lam, Tak-Wah}, keywords = {myown}, pages = {722–732}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Approximating the Generalized Minimum {Manhattan} Network Problem}, volume = 8283, year = 2013 }
Progress on Partial Edge Drawings Bruckdorfer, Till; Cornelsen, Sabine; Gutwenger, Carsten; Kaufmann, Michael; Montecchiani, Fabrizio; Nöllenburg, Martin; Wolff, Alexander in Proc. 20th Int. Sympos. Graph Drawing (GD’12), Lecture Notes in Computer Science, W. Didimo, M. Patrignani (Hrsg.) (2013). (Bd. 7704) 67–78.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{bcgkmnw-pped-GD12, author = {Bruckdorfer, Till and Cornelsen, Sabine and Gutwenger, Carsten and Kaufmann, Michael and Montecchiani, Fabrizio and N{\"o}llenburg, Martin and Wolff, Alexander}, booktitle = {Proc. 20th Int. Sympos. Graph Drawing (GD'12)}, editor = {Didimo, Walter and Patrignani, Maurizio}, keywords = {myown}, pages = {67–78}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Progress on Partial Edge Drawings}, volume = 7704, year = 2013 }
Universal Point Sets for Planar Graph Drawings with Circular Arcs Angelini, Patrizio; Eppstein, David; Fabrizio Frati, Michael Kaufmann; Lazard, Silvain; Tamara Mchedlidze, Monique Teillaud; Wolff, Alexander in Proc. 25th Canadian Conf. Comput. Geom. (CCCG’13) (2013). 117–122.
- [ BibTeX ]
- [ URL ]
- [ pdf ]
- [ slides ]
@inproceedings{aefklmtw-upspg-CCCG13, address = {Waterloo, ON, Canada}, author = {Angelini, Patrizio and Eppstein, David and Fabrizio Frati, Michael Kaufmann and Lazard, Silvain and Tamara Mchedlidze, Monique Teillaud and Wolff, Alexander}, booktitle = {Proc. 25th Canadian Conf. Comput. Geom. (CCCG'13)}, keywords = {myown}, pages = {117–122}, title = {Universal Point Sets for Planar Graph Drawings with Circular Arcs}, year = 2013 }
Two-Sided Boundary Labeling with Adjacent Sides Kindermann, Philipp; Niedermann, Benjamin; Rutter, Ignaz; Schaefer, Marcus; Schulz, André; Wolff, Alexander in Proc. 13th Int. Algorithms Data Struct. Symp. (WADS’13), Lecture Notes in Computer Science, F. Dehne, R. Solis-Oba, J.-R. Sack (Hrsg.) (2013). (Bd. 8037) 463–474.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{knrssw-2sbla-WADS13, author = {Kindermann, Philipp and Niedermann, Benjamin and Rutter, Ignaz and Schaefer, Marcus and Schulz, Andr{\'e} and Wolff, Alexander}, booktitle = {Proc. 13th Int. Algorithms Data Struct. Symp. (WADS'13)}, editor = {Dehne, F. and Solis-Oba, R. and Sack, J.-R.}, keywords = {myown}, pages = {463–474}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Two-Sided Boundary Labeling with Adjacent Sides}, volume = 8037, year = 2013 }
Drawing Metro Maps using Bézier Curves Fink, Martin; Haverkort, Herman; Nöllenburg, Martin; Roberts, Maxwell; Schuhmann, Julian; Wolff, Alexander in Proc. 20th Int. Sympos. Graph Drawing (GD’12), Lecture Notes in Computer Science, W. Didimo, M. Patrignani (Hrsg.) (2013). (Bd. 7704) 463–474.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{fhnrsw-dmmbc-GD12, author = {Fink, Martin and Haverkort, Herman and N{\"o}llenburg, Martin and Roberts, Maxwell and Schuhmann, Julian and Wolff, Alexander}, booktitle = {Proc. 20th Int. Sympos. Graph Drawing (GD'12)}, editor = {Didimo, Walter and Patrignani, Maurizio}, keywords = {myown}, pages = {463–474}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Metro Maps using {B{\'e}zier} Curves}, volume = 7704, year = 2013 }
Morphing Polylines Based on Least Squares Adjustment Peng, Dongliang; Haunert, Jan-Henrik; Wolff, Alexander in Proc. 16th ICA Generalisation Workshop (ICAGW’13) (2013).
- [ BibTeX ]
- [ pdf ]
@inproceedings{phw-mpbls-ICAGW13, author = {Peng, Dongliang and Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Proc. 16th ICA Generalisation Workshop (ICAGW'13)}, keywords = {myown}, note = {10 pages.}, title = {Morphing Polylines Based on Least Squares Adjustment}, year = 2013 }
Optimizing Active Ranges for Point Selection in Dynamic Maps Schwartges, Nadine; Allerkamp, Dennis; Haunert, Jan-Henrik; Wolff, Alexander in Proc. 16th ICA Generalisation Workshop (ICAGW’13) (2013).
- [ BibTeX ]
- [ URL ]
- [ slides ]
@inproceedings{sahw-oarps-ICAGW13, author = {Schwartges, Nadine and Allerkamp, Dennis and Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Proc. 16th ICA Generalisation Workshop (ICAGW'13)}, keywords = {myown}, note = {10 pages.}, title = {Optimizing Active Ranges for Point Selection in Dynamic Maps}, year = 2013 }
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles Fink, Martin; Haunert, Jan-Henrik; Mchedlidze, Tamara; Spoerhase, Joachim; Wolff, Alexander in Proc. Workshop Algorithms Comput. (WALCOM’12), Lecture Notes in Computer Science, M. S. Rahman, S.- ichi Nakano (Hrsg.) (2012). (Bd. 7157) 186–197.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
- [ poster ]
@inproceedings{fhmsw-dgvsp-WALCOM12, author = {Fink, Martin and Haunert, Jan-Henrik and Mchedlidze, Tamara and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. Workshop Algorithms Comput. (WALCOM'12)}, editor = {Rahman, {Md. Saidur} and Nakano, {Shin-ichi}}, keywords = {myown}, pages = {186–197}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles}, volume = 7157, year = 2012 }
Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs Schwartges, Nadine; Spoerhase, Joachim; Wolff, Alexander in Proc. 9th Workshop Approx. Online Algorithms (WAOA’11), Lecture Notes in Computer Science, R. Solis-Oba, G. Persiano (Hrsg.) (2012). (Bd. 7164) 77–88.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{ssw-aamls-WAOA12, author = {Schwartges, Nadine and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 9th Workshop Approx. Online Algorithms (WAOA'11)}, editor = {Solis-Oba, Roberto and Persiano, Giuseppe}, keywords = {myown}, pages = {77–88}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs}, volume = 7164, year = 2012 }
Approximating Minimum Manhattan Networks in Higher Dimensions Das, Aparna; Gansner, Emden R.; Kaufmann, Michael; Kobourov, Stephen; Spoerhase, Joachim; Wolff, Alexander in Proc. 19th Annu. Europ. Symp. on Algorithms (ESA’11), Lecture Notes in Computer Science, C. Demetrescu, M. M. Halldórsson (Hrsg.) (2011). (Bd. 6942) 49–60.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{dgkksw-ammnh-ESA11, author = {Das, Aparna and Gansner, Emden R. and Kaufmann, Michael and Kobourov, Stephen and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 19th Annu. Europ. Symp. on Algorithms (ESA'11)}, editor = {Demetrescu, Camil and Halld{\'o}rsson, Magn{\'u}s M.}, keywords = {myown}, pages = {49–60}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Approximating Minimum {Manhattan} Networks in Higher Dimensions}, volume = 6942, year = 2011 }
Manhattan-Geodesic Embedding of Planar Graphs Katz, Bastian; Krug, Marcus; Rutter, Ignaz; Wolff, Alexander in Proc. 17th Int. Sympos. Graph Drawing (GD’09), Lecture Notes in Computer Science, D. Eppstein, E. R. Gansner (Hrsg.) (2010). (Bd. 5849) 207–218.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{kkrw-mgepg-10, author = {Katz, Bastian and Krug, Marcus and Rutter, Ignaz and Wolff, Alexander}, booktitle = {Proc. 17th Int. Sympos. Graph Drawing (GD'09)}, editor = {Eppstein, David and Gansner, Emden R.}, keywords = {myown}, pages = {207–218}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Manhattan-Geodesic Embedding of Planar Graphs}, volume = 5849, year = 2010 }
Optimal and Topologically Safe Simplification of Building Footprints Haunert, Jan-Henrik; Wolff, Alexander in Proc. 18th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’10) (2010). 192–201.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
- [ pdf ]
@inproceedings{hw-otssb-ACMGIS10, author = {Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Proc. 18th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS'10)}, keywords = {myown}, pages = {192–201}, title = {Optimal and Topologically Safe Simplification of Building Footprints}, year = 2010 }
The Traveling Salesman Problem Under Squared Euclidean Distances de Berg, Marc; van Nijnatten, Fred; Sitters, René; Woeginger, Gerhard J.; Wolff, Alexander in Proc. 27th Int. Sympos. Theoretical Aspects Comput. Sci. (STACS’10), J.-Y. Marion, T. Schwentick (Hrsg.) (2010). 239–250.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{bnsww-tspus-STACS10, address = {Nancy}, author = {de Berg, Marc and van Nijnatten, Fred and Sitters, Ren{\'e} and Woeginger, Gerhard J. and Wolff, Alexander}, booktitle = {Proc. 27th Int. Sympos. Theoretical Aspects Comput. Sci. (STACS'10)}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, keywords = {myown}, pages = {239–250}, title = {The Traveling Salesman Problem Under Squared {Euclidean} Distances}, year = 2010 }
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 in Proc. 26th European Workshop Comput. Geom. (EuroCG’10) (2010). 73–76.
- [ BibTeX ]
- [ pdf ]
@inproceedings{dgkrtw-hagbg-EuroCG10, address = {Dortmund}, author = {de Berg, Mark and Gerrits, Dirk and Khosravi, Amirali and Rutter, Ignaz and Tsirogiannis, Constantinos and Wolff, Alexander}, booktitle = {Proc. 26th European Workshop Comput. Geom. (EuroCG'10)}, keywords = {myown}, pages = {73–76}, title = {How Alexander the Great Brought the Greeks Together While Inflicting Minimal Damage to the Barbarians}, year = 2010 }
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 Proc. 16th Int. Sympos. Graph Drawing (GD’08), Lecture Notes in Computer Science, I. G. Tollis, M. Patrignani (Hrsg.) (2009). (Bd. 5417) 324–335.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{bbbnosw-dcbth-09, author = {Buchin, Kevin and Buchin, Maike and Byrka, Jaroslaw and N\"ollenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo I. and Wolff, Alexander}, booktitle = {Proc. 16th Int. Sympos. Graph Drawing (GD'08)}, editor = {Tollis, Ioannis G. and Patrignani, Maurizio}, keywords = {myown}, pages = {324–335}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability}, volume = 5417, year = 2009 }
Drawing Binary Tanglegrams: An Experimental Evaluation Nöllenburg, Martin; Völker, Markus; Wolff, Alexander; Holten, Danny in Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX’09) (2009). 106–119.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{nvwh-dbtee-09, author = {N{\"o}llenburg, Martin and V{\"o}lker, Markus and Wolff, Alexander and Holten, Danny}, booktitle = {Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX'09)}, keywords = {myown}, pages = {106–119}, title = {Drawing Binary Tanglegrams: An Experimental Evaluation}, year = 2009 }
Constructability of Trip-lets Keiren, Jeroen; van Walderveen, Freek; Wolff, Alexander in Proc. 25th European Workshop on Computational Geometry (EuroCG’09), S. Langerman (Hrsg.) (2009).
- [ BibTeX ]
- [ pdf ]
@inproceedings{kww-ct-09, author = {Keiren, Jeroen and van Walderveen, Freek and Wolff, Alexander}, booktitle = {Proc. 25th European Workshop on Computational Geometry (EuroCG'09)}, editor = {Langerman, Stefan}, keywords = {myown}, title = {Constructability of Trip-lets}, year = 2009 }
Cover Contact Graphs Atienza, Nieves; de Castro, Natalia; Cortés, Carmen; Garrido, M. Ángeles; Grima, Clara I.; Hernández, Gregorio; Márquez, Alberto; Moreno, Auxiliadora; Nöllenburg, Martin; Portillo, José Ramon; Reyes, Pedro; Valenzuela, Jesús; Villar, Maria Trinidad; Wolff, Alexander in Proc. 15th Int. Sympos. Graph Drawing (GD’07), Lecture Notes in Computer Science, S.-H. Hong, T. Nishizeki, W. Quan (Hrsg.) (2008). (Bd. 4875) 171–182.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{accgghmmnprvvw-ccg-08, author = {Atienza, Nieves and de Castro, Natalia and Cort\'{e}s, Carmen and Garrido, M. {\'A}ngeles and Grima, Clara I. and Hern\'{a}ndez, Gregorio and M\'{a}rquez, Alberto and Moreno, Auxiliadora and N\"{o}llenburg, Martin and Portillo, Jos{\'e} Ramon and Reyes, Pedro and Valenzuela, Jes\'{u}s and Villar, Maria Trinidad and Wolff, Alexander}, booktitle = {Proc. 15th Int. Sympos. Graph Drawing (GD'07)}, editor = {Hong, Seok-Hee and Nishizeki, Takao and Quan, Wu}, keywords = {myown}, pages = {171–182}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Cover Contact Graphs}, volume = 4875, year = 2008 }
Trimming of Graphs, with Application to Point Labeling Erlebach, Thomas; Hagerup, Torben; Jansen, Klaus; Minzlaff, Moritz; Wolff, Alexander in Proc. 25th Int. Sympos. Theoretical Aspects Comput. Sci. (STACS’08), LIPIcs, S. Albers, P. Weil (Hrsg.) (2008). (Bd. 1) 265–276.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{ehjmw-tgapl-STACS08, address = {Bordeaux}, author = {Erlebach, Thomas and Hagerup, Torben and Jansen, Klaus and Minzlaff, Moritz and Wolff, Alexander}, booktitle = {Proc. 25th Int. Sympos. Theoretical Aspects Comput. Sci. (STACS'08)}, editor = {Albers, Susanne and Weil, Pascal}, keywords = {myown}, pages = {265–276}, series = {LIPIcs}, title = {Trimming of Graphs, with Application to Point Labeling}, volume = 1, year = 2008 }
Optimizing Active Ranges for Consistent Dynamic Map Labeling Been, Ken; Nöllenburg, Martin; Poon, Sheung-Hung; Wolff, Alexander in Proc. 24th Annu. ACM Sympos. Comput. Geom. (SoCG’08) (2008). 10–19.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{bnpw-oarcd-08, author = {Been, Ken and N{\"o}llenburg, Martin and Poon, Sheung-Hung and Wolff, Alexander}, booktitle = {Proc. 24th Annu. ACM Sympos. Comput. Geom. (SoCG'08)}, keywords = {myown}, pages = {10–19}, title = {Optimizing Active Ranges for Consistent Dynamic Map Labeling}, year = 2008 }
Optimal Simplification of Building Ground Plans Haunert, Jan-Henrik; Wolff, Alexander in Proc. 21st Congress Int. Society Photogrammetry Remote Sensing (ISPRS’08), Technical Commision II/3, Int. Archives of Photogrammetry, Remote Sensing and Spatial Informat. Sci. (2008). (Bd. XXXVII, Part B2) 373–378.
- [ BibTeX ]
- [ pdf ]
- [ slides ]
@inproceedings{hw-osbgp-ISPRS08, address = {Beijing}, author = {Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Proc. 21st Congress Int. Society Photogrammetry Remote Sensing (ISPRS'08), Technical Commision II/3}, keywords = {myown}, pages = {373–378}, series = {Int. Archives of Photogrammetry, Remote Sensing and Spatial Informat. Sci.}, title = {Optimal Simplification of Building Ground Plans}, volume = {XXXVII, Part B2}, year = 2008 }
Moving Vertices to Make Drawings Plane Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Wolff, Alexander in Proc. 15th Int. Sympos. Graph Drawing (GD’07), Lecture Notes in Computer Science, S.-H. Hong, T. Nishizeki, W. Quan (Hrsg.) (2008). (Bd. 4875) 101–112.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{gkosw-mvmdp-GD08, author = {Goaoc, Xavier and Kratochv{\'i}l, Jan and Okamoto, Yoshio and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. 15th Int. Sympos. Graph Drawing (GD'07)}, editor = {Hong, Seok-Hee and Nishizeki, Takao and Quan, Wu}, keywords = {myown}, pages = {101–112}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Moving Vertices to Make Drawings Plane}, volume = 4875, year = 2008 }
Augmenting the Connectivity of Planar and Geometric Graphs Rutter, Ignaz; Wolff, Alexander in Proc. Int. Conf. Topological Geom. Graph Theory (TGGT’08), Electronic Notes in Discrete Mathematics (2008). (Bd. 31) 53–56.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{rw-acpgg-08p, address = {Paris}, author = {Rutter, Ignaz and Wolff, Alexander}, booktitle = {Proc. Int. Conf. Topological Geom. Graph Theory (TGGT'08)}, keywords = {myown}, pages = {53–56}, series = {Electronic Notes in Discrete Mathematics}, title = {Augmenting the Connectivity of Planar and Geometric Graphs}, volume = 31, year = 2008 }
Computing Large Matchings Fast Rutter, Ignaz; Wolff, Alexander in Proc. 19th ACM-SIAM Sympos. Discrete Algorithms (SODA’08) (2008). 183–192.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{rw-clmf-08, author = {Rutter, Ignaz and Wolff, Alexander}, booktitle = {Proc. 19th ACM-SIAM Sympos. Discrete Algorithms (SODA'08)}, keywords = {myown}, pages = {183–192}, title = {Computing Large Matchings Fast}, year = 2008 }
Untangling a Planar Graph Spillner, Andreas; Wolff, Alexander in Proc. 34th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’08), Lecture Notes in Computer Science, V. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková (Hrsg.) (2008). (Bd. 4910) 473–484.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{sw-upg-08, author = {Spillner, Andreas and Wolff, Alexander}, booktitle = {Proc. 34th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'08)}, editor = {Geffert, Viliam and Karhum{\"a}ki, Juhani and Bertoni, Alberto and Preneel, Bart and N{\'a}vrat, Pavol and Bielikov{\'a}, M{\'a}ria}, keywords = {myown}, pages = {473–484}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Untangling a Planar Graph}, volume = 4910, year = 2008 }
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 Proc. 13th Conf. Computing: The Australasian Theory Sympos. (CATS’07), Conferences in Research and Practice in Information Technology, B. Jay, J. Gudmundsson (Hrsg.) (2007). (Bd. 65) 7–14.
- [ BibTeX ]
- [ URL ]
- [ pdf ]
@inproceedings{aaabbcknsw-coh-07, author = {Ahn, Hee-Kap and Alt, Helmut and Asano, Tetsuo and Bae, Sang Won and Brass, Peter and Cheong, Otfried and Knauer, Christian and Na, Hyeon-Suk and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. 13th Conf. Computing: The Australasian Theory Sympos. (CATS'07)}, editor = {Jay, Barry and Gudmundsson, Joachim}, keywords = {myown}, pages = {7–14}, publisher = {Australian Computer Society}, series = {Conferences in Research and Practice in Information Technology}, title = {Constructing Optimal Highways}, volume = 65, year = 2007 }
Morphing Polygonal Lines: A Step Towards Continuous Generalization Merrick, Damian; Nöllenburg, Martin; Wolff, Alexander; Benkert, Marc in Proc. 15th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK’07) (2007). 390–399.
- [ BibTeX ]
- [ URL ]
- [ pdf ]
@inproceedings{mnwb-mplst-GISRUK07, address = {Maynooth, Ireland}, author = {Merrick, Damian and N{\"o}llenburg, Martin and Wolff, Alexander and Benkert, Marc}, booktitle = {Proc. 15th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK'07)}, keywords = {myown}, pages = {390–399}, title = {Morphing Polygonal Lines: A Step Towards Continuous Generalization}, year = 2007 }
Straightening Drawings of Clustered Hierarchical Graphs Bereg, Sergey; Völker, Markus; Wolff, Alexander; Zhang, Yuanyi in Proc. 33rd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’07), Lecture Notes in Computer Science, J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plasil (Hrsg.) (2007). (Bd. 4362) 177–186.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bvwz-sdchg-07, author = {Bereg, Sergey and V{\"o}lker, Markus and Wolff, Alexander and Zhang, Yuanyi}, booktitle = {Proc. 33rd Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'07)}, editor = {van Leeuwen, Jan and Italiano, Giuseppe F. and van der Hoek, Wiebe and Meinel, Christoph and Sack, Harald and Plasil, Frantisek}, keywords = {myown}, pages = {177–186}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Straightening Drawings of Clustered Hierarchical Graphs}, volume = 4362, year = 2007 }
Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps Benkert, Marc; Nöllenburg, Martin; Uno, Takeaki; Wolff, Alexander in Proc. 14th Int. Sympos. Graph Drawing (GD’06), Lecture Notes in Computer Science, M. Kaufmann, D. Wagner (Hrsg.) (2007). (Bd. 4372) 270–281.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bnuw-miecw-07, author = {Benkert, Marc and N{\"o}llenburg, Martin and Uno, Takeaki and Wolff, Alexander}, booktitle = {Proc. 14th Int. Sympos. Graph Drawing (GD'06)}, editor = {Kaufmann, Michael and Wagner, Dorothea}, keywords = {myown}, pages = {270–281}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps}, volume = 4372, year = 2007 }
Morphing Polygonal Lines: A Step Towards Continuous Generalization Merrick, Damian; Nöllenburg, Martin; Wolff, Alexander; Benkert, Marc in Proc. 23rd European Workshop on Computational Geometry (EWCG’07), O. Aichholzer, T. Hackl (Hrsg.) (2007). 6–9.
- [ BibTeX ]
- [ pdf ]
@inproceedings{mnwb-mplst-EWCG07, address = {Graz}, author = {Merrick, Damian and N{\"o}llenburg, Martin and Wolff, Alexander and Benkert, Marc}, booktitle = {Proc. 23rd European Workshop on Computational Geometry (EWCG'07)}, editor = {Aichholzer, Oswin and Hackl, Thomas}, keywords = {myown}, pages = {6–9}, title = {Morphing Polygonal Lines: A Step Towards Continuous Generalization}, year = 2007 }
Matching Points with Rectangles and Squares Bereg, Sergey; Mutsanas, Nikolaus; Wolff, Alexander in Proc. 32nd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’06), Lecture Notes in Computer Science, J. r’i} Wiedermann, J. Stuller, G. Tel, J. Pokorn’y}}, M. Bieliková (Hrsg.) (2006). (Bd. 3831) 177–186.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{bmw-mprs-06, author = {Bereg, Sergey and Mutsanas, Nikolaus and Wolff, Alexander}, booktitle = {Proc. 32nd Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'06)}, editor = {Wiedermann, Ji{\v r}{\'\i} and Stuller, Julius and Tel, Gerard and Pokorn{\'y}, Jaroslav and Bielikov{\'a}, M{\'a}ria}, keywords = {myown}, pages = {177–186}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Matching Points with Rectangles and Squares}, volume = 3831, year = 2006 }
Generalization of Land Cover Maps by Mixed Integer Programming Haunert, Jan-Henrik; Wolff, Alexander in Proc. 14th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’06) (2006). 75–82.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
- [ pdf ]
@inproceedings{hw-glcmm-ACMGIS06, author = {Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Proc. 14th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS'06)}, keywords = {myown}, pages = {75–82}, title = {Generalization of Land Cover Maps by Mixed Integer Programming}, year = 2006 }
Improved Fixed-Parameter Algorithms for Non-Crossing Subgraphs Halldórsson, Magnús M.; Wolff, Alexander; Tokuyama, Takeshi in Proc. ICALP Affiliated Workshop on Improving Exponential-Time Algorithms (iETA’06) (2006). 31–38.
- [ BibTeX ]
- [ pdf ]
@inproceedings{htw-ifpan-iETA06, address = {Venezia}, author = {Halld{\'o}rsson, Magn{\'u}s M. and Wolff, Alexander and Tokuyama, Takeshi}, booktitle = {Proc. ICALP Affiliated Workshop on Improving Exponential-Time Algorithms (iETA'06)}, keywords = {myown}, pages = {31–38}, title = {Improved Fixed-Parameter Algorithms for Non-Crossing Subgraphs}, year = 2006 }
A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem Benkert, Marc; Gudmundsson, Joachim; Knauer, Christian; Moet, Esther; van Oostrum, René; Wolff, Alexander in Proc. 12th Annu. Int. Comput. Combinatorics Conf. (COCOON’06), Lecture Notes in Computer Science, D. Z. Chen, D.-T. Lee (Hrsg.) (2006). (Bd. 4112) 166–175.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bgkmow-ptaag-06, author = {Benkert, Marc and Gudmundsson, Joachim and Knauer, Christian and Moet, Esther and van Oostrum, Ren{\'e} and Wolff, Alexander}, booktitle = {Proc. 12th Annu. Int. Comput. Combinatorics Conf. (COCOON'06)}, editor = {Chen, Danny Z. and Lee, Der-Tsai}, keywords = {myown}, pages = {166–175}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem}, volume = 4112, year = 2006 }
A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem Benkert, Marc; Gudmundsson, Joachim; Knauer, Christian; Moet, Esther; van Oostrum, René; Wolff, Alexander in Proc. 22nd European Workshop on Computational Geometry (EWCG’06) (2006). 141–144.
- [ BibTeX ]
- [ pdf ]
@inproceedings{bgkmow-ptaag-06i, address = {Delphi}, author = {Benkert, Marc and Gudmundsson, Joachim and Knauer, Christian and Moet, Esther and van Oostrum, Ren{\'e} and Wolff, Alexander}, booktitle = {Proc. 22nd European Workshop on Computational Geometry (EWCG'06)}, keywords = {myown}, pages = {141–144}, title = {A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem}, year = 2006 }
A Mixed-Integer Program for Drawing High-Quality Metro Maps Nöllenburg, Martin; Wolff, Alexander in Proc. 13th Int. Sympos. Graph Drawing (GD’05), Lecture Notes in Computer Science, P. Healy, N. S. Nikolov (Hrsg.) (2006). (Bd. 3843) 321–333.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{nw-mipdh-06, author = {N{\"o}llenburg, Martin and Wolff, Alexander}, booktitle = {Proc. 13th Int. Sympos. Graph Drawing (GD'05)}, editor = {Healy, Patrick and Nikolov, Nikola S.}, keywords = {myown}, pages = {321–333}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {A Mixed-Integer Program for Drawing High-Quality Metro Maps}, volume = 3843, year = 2006 }
Pseudo-Convex Decomposition of Simple Polygons Gerdjikov, Stefan; Wolff, Alexander in Proc. 22nd European Workshop on Computational Geometry (EWCG’06) (2006). 13–16.
- [ BibTeX ]
- [ pdf ]
@inproceedings{gw-pcdsp-EWCG06, address = {Delphi}, author = {Gerdjikov, Stefan and Wolff, Alexander}, booktitle = {Proc. 22nd European Workshop on Computational Geometry (EWCG'06)}, keywords = {myown}, pages = {13–16}, title = {Pseudo-Convex Decomposition of Simple Polygons}, year = 2006 }
A New Approximation Algorithm for Labeling Weighted Points with Sliding Labels Erlebach, Thomas; Hagerup, Torben; Jansen, Klaus; Minzlaff, Moritz; Wolff, Alexander in Proc. 22nd European Workshop on Computational Geometry (EWCG’06) (2006). 137–140.
- [ BibTeX ]
- [ pdf ]
@inproceedings{ehjmw-naalw-06, address = {Delphi}, author = {Erlebach, Thomas and Hagerup, Torben and Jansen, Klaus and Minzlaff, Moritz and Wolff, Alexander}, booktitle = {Proc. 22nd European Workshop on Computational Geometry (EWCG'06)}, keywords = {myown}, pages = {137–140}, title = {A New Approximation Algorithm for Labeling Weighted Points with Sliding Labels}, year = 2006 }
Constructing Interference-Minimal Networks Benkert, Marc; Gudmundsson, Joachim; Haverkort, Herman; Wolff, Alexander in Proc. 32nd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’06), Lecture Notes in Computer Science, J. Wiedermann, J. Stuller, G. Tel, J. Pokorn’y}}, M. Bieliková (Hrsg.) (2006). (Bd. 3831) 166–175.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bghw-cimn-06, author = {Benkert, Marc and Gudmundsson, Joachim and Haverkort, Herman and Wolff, Alexander}, booktitle = {Proc. 32nd Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'06)}, editor = {Wiedermann, Ji\v{r}\'{\i} and Stuller, Julius and Tel, Gerard and Pokorn\'{y}, Jaroslav and Bielikov\'{a}, M\'{a}ria}, keywords = {myown}, pages = {166–175}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Constructing Interference-Minimal Networks}, volume = 3831, year = 2006 }
Routing by Landmarks Rüetschi, Urs-Jakob; Caduff, David; Timpf, Sabine; Schulz, Frank; Wolff, Alexander in Proc. 6th Swiss Transport Research Conf. (STRC’06) (2006).
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
- [ pdf ]
A route in a network can be described as a sequence of nodes. Given a route, travellers need directions to follow it, which are preferably expressed as a sequence of instructions, as for instance, "face towards the tower" and "move along the river". This paper presents a method to find routes in a network with the property that they can be described by a simple sequence of instructions. The key problems that we need to solve are (1)~how to attribute landmark information to the network and (2)~how to find an optimal route. We approach the first problem by using landmarks as parts of instructions and mapping instructions to sets of edges in the network. The second problem can be solved by building an auxiliary graph such that a standard Dijkstra shortest path algorithm can be used to find optimal routes. Preliminary tests indicate that our approaches produce good results.

@inproceedings{rcswt-rl-06, abstract = {A route in a network can be described as a sequence of nodes. Given a route, travellers need directions to follow it, which are preferably expressed as a sequence of instructions, as for instance, "face towards the tower" and "move along the river". This paper presents a method to find routes in a network with the property that they can be described by a simple sequence of instructions. The key problems that we need to solve are (1) how to attribute landmark information to the network and (2) how to find an optimal route. We approach the first problem by using landmarks as parts of instructions and mapping instructions to sets of edges in the network. The second problem can be solved by building an auxiliary graph such that a standard Dijkstra shortest path algorithm can be used to find optimal routes. Preliminary tests indicate that our approaches produce good results.}, address = {Ascona}, author = {R{\"u}etschi, Urs-Jakob and Caduff, David and Timpf, Sabine and Schulz, Frank and Wolff, Alexander}, booktitle = {Proc. 6th Swiss Transport Research Conf. (STRC'06)}, keywords = {myown}, note = {CD-ROM}, title = {Routing by Landmarks}, year = 2006 }
Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps Bekos, Michael A.; Kaufmann, Michael; Symvonis, Antonios; Wolff, Alexander in Proc. 12th Int. Sympos. Graph Drawing (GD’04), Lecture Notes in Computer Science, J. Pach (Hrsg.) (2005). (Bd. 3383) 49–59.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
In this paper, we present em boundary labeling, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the points. Then we connect each label to its point such that no two connections intersect. Such an approach is common e.g. in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem.

@inproceedings{bksw-blmea-05, abstract = {In this paper, we present {\em boundary labeling}, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the points. Then we connect each label to its point such that no two connections intersect. Such an approach is common e.g.\ in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem.}, author = {Bekos, Michael A. and Kaufmann, Michael and Symvonis, Antonios and Wolff, Alexander}, booktitle = {Proc. 12th Int. Sympos. Graph Drawing (GD'04)}, editor = {Pach, J{\'a}nos}, keywords = {myown}, pages = {49–59}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps}, volume = 3383, year = 2005 }
Delineating Boundaries for Imprecise Regions Reinbacher, Iris; Benkert, Marc; van Kreveld, Marc; Mitchell, Joseph S.B.; Wolff, Alexander in Proc. 13th Annu. Europ. Symp. on Algorithms (ESA’05), Lecture Notes in Computer Science, G. S. Brodal, S. Leonardi (Hrsg.) (2005). (Bd. 3669) 143–154.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{rbkmw-dbir-05, author = {Reinbacher, Iris and Benkert, Marc and van Kreveld, Marc and Mitchell, Joseph S.B. and Wolff, Alexander}, booktitle = {Proc. 13th Annu. Europ. Symp. on Algorithms (ESA'05)}, editor = {Brodal, Gerth St{\o}lting and Leonardi, Stefano}, keywords = {myown}, pages = {143–154}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Delineating Boundaries for Imprecise Regions}, volume = 3669, year = 2005 }
Farthest-Point Queries with Geometric and Combinatorial Constraints Daescu, Ovidiu; Mi, Ningfang; Shin, Chan-Su; Wolff, Alexander in Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04), Lecture Notes in Computer Science, J. Akiyama, M. Kano, X. Tan (Hrsg.) (2005). (Bd. 3742) 62–75.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{dmsw-fpqgc-05, author = {Daescu, Ovidiu and Mi, Ningfang and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04)}, editor = {Akiyama, Jin and Kano, Mikio and Tan, Xuehou}, keywords = {myown}, pages = {62–75}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Farthest-Point Queries with Geometric and Combinatorial Constraints}, volume = 3742, year = 2005 }
The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation Benkert, Marc; Widmann, Florian; Wolff, Alexander in Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04), Lecture Notes in Computer Science, J. Akiyama, M. Kano, X. Tan (Hrsg.) (2005). (Bd. 3742) 16–28.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bww-mmnpf-05, author = {Benkert, Marc and Widmann, Florian and Wolff, Alexander}, booktitle = {Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04)}, editor = {Akiyama, Jin and Kano, Mikio and Tan, Xuehou}, keywords = {myown}, pages = {16–28}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {The Minimum {Manhattan} Network Problem: A Fast Factor-3 Approximation}, volume = 3742, year = 2005 }
Constructing the City Voronoi Diagram Faster Görke, Robert; Wolff, Alexander in Proc. 2nd Int. Symp. on Voronoi Diagrams in Science and Engineering (VD’05) (2005). 162–172.
- [ BibTeX ]
- [ pdf ]
@inproceedings{gw-ccvdf-VD05, address = {Seoul}, author = {G{\"o}rke, Robert and Wolff, Alexander}, booktitle = {Proc. 2nd Int. Symp. on Voronoi Diagrams in Science and Engineering (VD'05)}, keywords = {myown}, pages = {162–172}, title = {Constructing the City {Voronoi} Diagram Faster}, year = 2005 }
Spanning Trees with Few Crossings in Geometric and Topological Graphs Knauer, Christian; Schramm, Étienne; Spillner, Andreas; Wolff, Alexander in Proc. 21st European Workshop on Computational Geometry (EWCG’05) (2005). 195–198.
- [ BibTeX ]
- [ pdf ]
@inproceedings{kssw-stfcg-05, address = {Eindhoven}, author = {Knauer, Christian and Schramm, {\'E}tienne and Spillner, Andreas and Wolff, Alexander}, booktitle = {Proc. 21st European Workshop on Computational Geometry (EWCG'05)}, keywords = {myown}, pages = {195–198}, title = {Spanning Trees with Few Crossings in Geometric and Topological Graphs}, year = 2005 }
Constructing the City Voronoi Diagram Faster Görke, Robert; Wolff, Alexander in Proc. 21st European Workshop on Computational Geometry (EWCG’05) (2005). 155–158.
- [ BibTeX ]
- [ pdf ]
@inproceedings{gw-ccvdf-EWCG05, address = {Eindhoven}, author = {G{\"o}rke, Robert and Wolff, Alexander}, booktitle = {Proc. 21st European Workshop on Computational Geometry (EWCG'05)}, keywords = {myown}, pages = {155–158}, title = {Constructing the City {Voronoi} Diagram Faster}, year = 2005 }
Delineating Boundaries for Imprecise Regions Reinbacher, Iris; Benkert, Marc; van Kreveld, Marc; Wolff, Alexander in Proc. 21st European Workshop on Computational Geometry (EWCG’05) (2005). 127–130.
- [ BibTeX ]
- [ pdf ]
@inproceedings{rbkw-dbir-05, address = {Eindhoven}, author = {Reinbacher, Iris and Benkert, Marc and van Kreveld, Marc and Wolff, Alexander}, booktitle = {Proc. 21st European Workshop on Computational Geometry (EWCG'05)}, keywords = {myown}, pages = {127–130}, title = {Delineating Boundaries for Imprecise Regions}, year = 2005 }
Constructing Interference-Minimal Networks Benkert, Marc; Gudmundsson, Joachim; Haverkort, Herman; Wolff, Alexander in Proc. 21st European Workshop on Computational Geometry (EWCG’05) (2005). 203–206.
- [ BibTeX ]
- [ pdf ]
@inproceedings{bghw-cimn-05, address = {Eindhoven}, author = {Benkert, Marc and Gudmundsson, Joachim and Haverkort, Herman and Wolff, Alexander}, booktitle = {Proc. 21st European Workshop on Computational Geometry (EWCG'05)}, keywords = {myown}, pages = {203–206}, title = {Constructing Interference-Minimal Networks}, year = 2005 }
Configurations with Few Crossings in Topological Graphs Knauer, Christian; Schramm, Étienne; Spillner, Andreas; Wolff, Alexander in Proc. 16th Annu. Int. Symp. Algorithms Comput. (ISAAC’05), Lecture Notes in Computer Science, X. Deng, D.-Z. Du (Hrsg.) (2005). (Bd. 3827) 604–613.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
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.

@inproceedings{kssw-cfctg-05, abstract = {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.}, author = {Knauer, Christian and Schramm, {\'E}tienne and Spillner, Andreas and Wolff, Alexander}, booktitle = {Proc. 16th Annu. Int. Symp. Algorithms Comput. (ISAAC'05)}, editor = {Deng, Xiaotie and Du, Ding-Zhu}, keywords = {myown}, pages = {604–613}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Configurations with Few Crossings in Topological Graphs}, volume = 3827, year = 2005 }
Optimal Spanners for Axis-Aligned Rectangles Asano, Tetsuo; de Berg, Mark; Cheong, Otfried; Everett, Hazel; Haverkort, Herman; Katoh, Naoki; Wolff, Alexander in Proc. 20th European Workshop on Computational Geometry (EWCG’04) (2004). 97–100.
- [ BibTeX ]
- [ pdf ]
@inproceedings{abcehkw-osaar-04, address = {Sevilla}, author = {Asano, Tetsuo and de Berg, Mark and Cheong, Otfried and Everett, Hazel and Haverkort, Herman and Katoh, Naoki and Wolff, Alexander}, booktitle = {Proc. 20th European Workshop on Computational Geometry (EWCG'04)}, keywords = {myown}, pages = {97–100}, title = {Optimal Spanners for Axis-Aligned Rectangles}, year = 2004 }
Farthest-Point Queries with Geometric and Combinatorial Constraints Daescu, Ovidiu; Mi, Ningfang; Shin, Chan-Su; Wolff, Alexander in Proc. 20th European Workshop on Computational Geometry (EWCG’04) (2004). 45–48.
- [ BibTeX ]
- [ pdf ]
@inproceedings{dmsw-fpqgc-04, address = {Sevilla}, author = {Daescu, Ovidiu and Mi, Ningfang and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. 20th European Workshop on Computational Geometry (EWCG'04)}, keywords = {myown}, pages = {45–48}, title = {Farthest-Point Queries with Geometric and Combinatorial Constraints}, year = 2004 }
Web-Based Delineation of Imprecise Regions Arampatzis, Avi; van Kreveld, Marc; Reinbacher, Iris; Jones, Christopher B.; Vaid, Subodh; Clough, Paul; Joho, Hideo; Sanderson, Mark; Benkert, Marc; Wolff, Alexander in Proc. Workshop on Geographic Information Retrieval at SIGIR’04 (2004).
- [ BibTeX ]
- [ pdf ]
@inproceedings{qkrjvcjsbw-wbdir-04, address = {Sheffield}, author = {Arampatzis, Avi and van Kreveld, Marc and Reinbacher, Iris and Jones, Christopher B. and Vaid, Subodh and Clough, Paul and Joho, Hideo and Sanderson, Mark and Benkert, Marc and Wolff, Alexander}, booktitle = {Proc. Workshop on Geographic Information Retrieval at SIGIR'04}, keywords = {myown}, title = {Web-Based Delineation of Imprecise Regions}, year = 2004 }
Farthest-Point Queries with Geometric and Combinatorial Constraints Daescu, Ovidiu; Mi, Ningfang; Shin, Chan-Su; Wolff, Alexander in Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04) (2004). 110–111.
- [ BibTeX ]
- [ pdf ]
@inproceedings{dmsw-fpqgc-04i, address = {Tokyo}, author = {Daescu, Ovidiu and Mi, Ningfang and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04)}, keywords = {myown}, pages = {110–111}, title = {Farthest-Point Queries with Geometric and Combinatorial Constraints}, year = 2004 }
The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation Benkert, Marc; Widmann, Florian; Wolff, Alexander in Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04) (2004). 85–86.
- [ BibTeX ]
- [ pdf ]
@inproceedings{bww-mmnpf-04, address = {Tokyo}, author = {Benkert, Marc and Widmann, Florian and Wolff, Alexander}, booktitle = {Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG'04)}, keywords = {myown}, pages = {85–86}, title = {The Minimum {Manhattan} Network Problem: A Fast Factor-3 Approximation}, year = 2004 }
The Minimum Manhattan Network Problem: Approximations and Exact Solutions Wolff, Alexander; Benkert, Marc; Shirabe, Takeshi in Proc. 20th European Workshop on Computational Geometry (EWCG’04) (2004). 209–212.
- [ BibTeX ]
- [ pdf ]
@inproceedings{wbs-mmnpa-04, address = {Sevilla}, author = {Wolff, Alexander and Benkert, Marc and Shirabe, Takeshi}, booktitle = {Proc. 20th European Workshop on Computational Geometry (EWCG'04)}, keywords = {myown}, pages = {209–212}, title = {The Minimum {Manhattan} Network Problem: Approximations and Exact Solutions}, year = 2004 }
Algorithms for the Placement of Diagrams on Maps van Kreveld, Marc; Schramm, Étienne; Wolff, Alexander in Proc. 12th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’04), D. Pfoder, I. F. Cruz, M. Ronthaler (Hrsg.) (2004). 222–231.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
- [ DOI ]
- [ pdf ]
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.

@inproceedings{ksw-apdm-04, abstract = {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.}, author = {van Kreveld, Marc and Schramm, {\'E}tienne and Wolff, Alexander}, booktitle = {Proc. 12th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS'04)}, editor = {Pfoder, Dieter and Cruz, Isabel F. and Ronthaler, Marc}, keywords = {myown}, pages = {222–231}, title = {Algorithms for the Placement of Diagrams on Maps}, year = 2004 }
Facility Location and the Geometric Minimum-Diameter Spanning Tree Gudmundsson, Joachim; Haverkort, Herman; Park, Sang-Min; Shin, Chan-Su; Wolff, Alexander in Proc. 5th Int. Workshop Approx. Algorithms Combin. Optim. (APPROX’02), Lecture Notes in Computer Science, K. Jansen, S. Leonardi, V. Vazirani (Hrsg.) (2002). (Bd. 2462) 146–160.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{ghpsw-flgmd-02, author = {Gudmundsson, Joachim and Haverkort, Herman and Park, Sang-Min and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. 5th Int. Workshop Approx. Algorithms Combin. Optim. (APPROX'02)}, editor = {Jansen, Klaus and Leonardi, Stefano and Vazirani, Vijay}, keywords = {myown}, pages = {146–160}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Facility Location and the Geometric Minimum-Diameter Spanning Tree}, volume = 2462, year = 2002 }
Approximating the Geometric Minimum-Diameter Spanning Tree Gudmundsson, Joachim; Haverkort, Herman; Park, Sang-Min; Shin, Chan-Su; Wolff, Alexander in Proc. 18th European Workshop on Computational Geometry (EWCG’02) (2002). 41–45.
- [ BibTeX ]
- [ pdf ]
@inproceedings{ghpsw-agmds-02, address = {War\-szawa}, author = {Gudmundsson, Joachim and Haverkort, Herman and Park, Sang-Min and Shin, Chan-Su and Wolff, Alexander}, booktitle = {Proc. 18th European Workshop on Computational Geometry (EWCG'02)}, keywords = {myown}, pages = {41–45}, title = {Approximating the Geometric Minimum-Diameter Spanning Tree}, year = 2002 }
Labeling Points with Weights Poon, Sheung-Hung; Shin, Chan-Su; Strijk, Tycho; Wolff, Alexander in Proc. 17th European Workshop on Computational Geometry (EWCG’01) (2001). 97–100.
- [ Abstract ]
- [ BibTeX ]
- [ pdf ]
Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually refered 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. 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 unit-height labels. We give an $$O(n\log n)$$-time factor-2 approximation algorithm for fixed-position models and the first algorithm for labeling weighted points with sliding labels. Its approximation factor is $$(2+\varepsilon)$$ and its runtime in $$O(n^2/\varepsilon)$$ for any $$\varepsilon>0$$.

@inproceedings{pssw-lpw-01, abstract = {Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually refered 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. 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 unit-height labels. We give an $O(n\log n)$-time factor-2 approximation algorithm for fixed-position models and the first algorithm for labeling weighted points with sliding labels. Its approximation factor is $(2+\varepsilon)$ and its runtime in $O(n^2/\varepsilon)$ for any $\varepsilon>0$.}, address = {Berlin}, author = {Poon, Sheung-Hung and Shin, Chan-Su and Strijk, Tycho and Wolff, Alexander}, booktitle = {Proc. 17th European Workshop on Computational Geometry (EWCG'01)}, keywords = {myown}, pages = {97–100}, title = {Labeling Points with Weights}, year = 2001 }
Labeling Subway Lines Garrido, Mari Ángeles; Iturriaga, Claudia; Márquez, Alberto; Portillo, José Ramon; Reyes, Pedro; Wolff, Alexander in Proc. 12th Annu. Int. Symp. Algorithms Comput. (ISAAC’01), Lecture Notes in Computer Science, P. Eades, T. Takaoka (Hrsg.) (2001). (Bd. 2223) 649–659.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
Graphical features on map, charts, diagrams and graph drawings usually must be annotated with text labels in order to convey their meaning. In this paper we focus on a problem that arises when labeling schematized maps, e.g. for subway networks. We present algorithms for labeling points on a line with axis-parallel rectangular labels of equal height. Our aim is to maximize label size under the constraint that all points must be labeled. Even a seemingly strong simplification of the general point-labeling problem, namely to decide whether a set of points on a horizontal line can be labeled with sliding rectangular labels, turns out to be weakly NP-complete. This is the first labeling problem that is known to belong to this class. We give a pseudo-polynomial time algorithm for it. In case of a sloping line points can be labeled with maximum-size square labels in $$O(n \log n)$$ time if four label positions per point are allowed and in $$O(n^3\log n)$$ time if labels can slide. We also investigate rectangular labels.

@inproceedings{gimprw-lsl-01, abstract = {Graphical features on map, charts, diagrams and graph drawings usually must be annotated with text labels in order to convey their meaning. In this paper we focus on a problem that arises when labeling schematized maps, e.g. for subway networks. We present algorithms for labeling points on a line with axis-parallel rectangular labels of equal height. Our aim is to maximize label size under the constraint that all points must be labeled. Even a seemingly strong simplification of the general point-labeling problem, namely to decide whether a set of points on a horizontal line can be labeled with sliding rectangular labels, turns out to be weakly NP-complete. This is the first labeling problem that is known to belong to this class. We give a pseudo-polynomial time algorithm for it. In case of a sloping line points can be labeled with maximum-size square labels in $O(n \log n)$ time if four label positions per point are allowed and in $O(n^3\log n)$ time if labels can slide. We also investigate rectangular labels.}, author = {Garrido, Mari {\'A}ngeles and Iturriaga, Claudia and M{\'a}rquez, Alberto and Portillo, Jos{\'e} Ramon and Reyes, Pedro and Wolff, Alexander}, booktitle = {Proc. 12th Annu. Int. Symp. Algorithms Comput. (ISAAC'01)}, editor = {Eades, Peter and Takaoka, Tadao}, keywords = {myown}, pages = {649–659}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Labeling Subway Lines}, volume = 2223, year = 2001 }
Etiquetado de puntos alineados Garrido, Mari Ángeles; Márquez, Alberto; Iturriaga, Claudia; Portillo, José Ramon; Reyes, Pedro; Wolff, Alexander in Proc. IX Encuentros de Geometría Computacional (EGC’01) (2001). 285–294.
- [ BibTeX ]
@inproceedings{gmiprw-epa-EGC01, address = {Girona}, author = {Garrido, Mari {\'A}ngeles and M{\'a}rquez, Alberto and Iturriaga, Claudia and Portillo, Jos{\'e} Ramon and Reyes, Pedro and Wolff, Alexander}, booktitle = {Proc. IX Encuentros de Geometr{\'i}a Computacional (EGC'01)}, keywords = {myown}, pages = {285–294}, title = {Etiquetado de puntos alineados}, year = 2001 }
Labeling Points with Weights Poon, Sheung-Hung; Shin, Chan-Su; Strijk, Tycho; Wolff, Alexander in Proc. 12th Annu. Int. Symp. Algorithms Comput. (ISAAC’01), Lecture Notes in Computer Science, P. Eades, T. Takaoka (Hrsg.) (2001). (Bd. 2223) 610–622.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{pssw-lpw-01i, author = {Poon, Sheung-Hung and Shin, Chan-Su and Strijk, Tycho and Wolff, Alexander}, booktitle = {Proc. 12th Annu. Int. Symp. Algorithms Comput. (ISAAC'01)}, editor = {Eades, Peter and Takaoka, Tadao}, keywords = {myown}, pages = {610–622}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Labeling Points with Weights}, volume = 2223, year = 2001 }
Ein neuer Algorithmus zur Beschriftung von Punkten mit je zwei Kreisen Thon, Michael; Wolff, Alexander; Xu, Yinfeng in Tagungsband der Informatiktage, Gesellschaft für Informatik e.V. (Hrsg.) (2000).
- [ BibTeX ]
@inproceedings{twx-nabp2-00, author = {Thon, Michael and Wolff, Alexander and Xu, Yinfeng}, booktitle = {Tagungsband der Informatiktage}, editor = {{Gesellschaft f{\"u}r Informatik e.V.}}, keywords = {myown}, title = {{Ein neuer Algorithmus zur Beschriftung von Punkten mit je zwei Kreisen}}, year = 2000 }
New Algorithms for Two-Label Point Labeling Qin, Zhongping; Wolff, Alexander; Xu, Yinfeng; Zhu, Binhai in Proc. 8th Annu. Europ. Symp. on Algorithms (ESA’00), Lecture Notes in Computer Science, M. Paterson (Hrsg.) (2000). (Bd. 1879) 368–379.
- [ BibTeX ]
- [ DOI ]
@inproceedings{qwxz-na2lp-00, author = {Qin, Zhongping and Wolff, Alexander and Xu, Yinfeng and Zhu, Binhai}, booktitle = {Proc. 8th Annu. Europ. Symp. on Algorithms (ESA'00)}, editor = {Paterson, Mike}, keywords = {myown}, pages = {368–379}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {New Algorithms for Two-Label Point Labeling}, volume = 1879, year = 2000 }
A Better Lower Bound for Two-Circle Point Labeling Wolff, Alexander; Thon, Michael; Xu, Yinfeng in Proc. 11th Annu. Int. Symp. Algorithms Comput. (ISAAC’00), Lecture Notes in Computer Science, D. Lee, S.-H. Teng (Hrsg.) (2000). (Bd. 1969) 422–431.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{wtx-blb2c-00, author = {Wolff, Alexander and Thon, Michael and Xu, Yinfeng}, booktitle = {Proc. 11th Annu. Int. Symp. Algorithms Comput. (ISAAC'00)}, editor = {Lee, D.T. and Teng, S.-H.}, keywords = {myown}, pages = {422–431}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {A Better Lower Bound for Two-Circle Point Labeling}, volume = 1969, year = 2000 }
Towards an Evaluation of Quality for Label Placement Methods van Dijk, Steven; van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander in Proc. 19th Int. Cartographic Conf. (ICA’99) (1999). 905–913.
- [ Abstract ]
- [ BibTeX ]
- [ pdf ]
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.

@inproceedings{dksw-teqlp-99, abstract = {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.}, address = {Ottawa}, author = {van Dijk, Steven and van Kreveld, Marc and Strijk, Tycho and Wolff, Alexander}, booktitle = {Proc. 19th Int. Cartographic Conf. (ICA'99)}, keywords = {myown}, organization = {Int. Cartographic Association}, pages = {905–913}, title = {Towards an Evaluation of Quality for Label Placement Methods}, year = 1999 }
A Combinatorial Framework for Map Labeling Wagner, Frank; Wolff, Alexander in Proc. 6th Int. Sympos. Graph Drawing (GD’98), Lecture Notes in Computer Science, S. H. Whitesides (Hrsg.) (1999). (Bd. 1547) 316–331.
- [ BibTeX ]
- [ DOI ]
@inproceedings{ww-cfml-99, author = {Wagner, Frank and Wolff, Alexander}, booktitle = {Proc. 6th Int. Sympos. Graph Drawing (GD'98)}, editor = {Whitesides, Sue H.}, keywords = {myown}, pages = {316–331}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {A Combinatorial Framework for Map Labeling}, volume = 1547, year = 1999 }
A Simple and Efficient Algorithm for High-Quality Line Labeling Agarwal, Pankaj K.; Knipping, Lars; van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander in Proc. 15th European Workshop on Computational Geometry (EWCG’99) (1999). 93–96.
- [ BibTeX ]
@inproceedings{akksw-seahq-99, address = {Sophia-Antipolis}, author = {Agarwal, Pankaj K. and Knipping, Lars and van Kreveld, Marc and Strijk, Tycho and Wolff, Alexander}, booktitle = {Proc. 15th European Workshop on Computational Geometry (EWCG'99)}, keywords = {myown}, pages = {93–96}, title = {A Simple and Efficient Algorithm for High-Quality Line Labeling}, year = 1999 }
A Simple and Efficient Algorithm for High-Quality Line Labeling Wolff, Alexander; Knipping, Lars; van Kreveld, Marc; Strijk, Tycho; Agarwal, Pankaj K. in Proc. 7th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK’99), D. Martin, F. Wu (Hrsg.) (1999). 146–150.
- [ BibTeX ]
@inproceedings{wkksa-seahq-99, address = {Southampton}, author = {Wolff, Alexander and Knipping, Lars and van Kreveld, Marc and Strijk, Tycho and Agarwal, Pankaj K.}, booktitle = {Proc. 7th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK'99)}, editor = {Martin, David and Wu, Fulong}, keywords = {myown}, pages = {146–150}, title = {A Simple and Efficient Algorithm for High-Quality Line Labeling}, year = 1999 }
Point Set Labeling with Sliding Labels van Kreveld, Marc; Strijk, Tycho; Wolff, Alexander in Proc. 14th Annu. ACM Sympos. Comput. Geom. (SoCG’98) (1998). 337–346.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
@inproceedings{ksw-pslsl-98, author = {van Kreveld, Marc and Strijk, Tycho and Wolff, Alexander}, booktitle = {Proc. 14th Annu. ACM Sympos. Comput. Geom. (SoCG'98)}, keywords = {myown}, pages = {337–346}, title = {Point Set Labeling with Sliding Labels}, year = 1998 }
MakeIt! -- Generating and Maintaining Makefiles Automatically Schönherr, Sven; Wolff, Alexander in Proc. Workshop on Algorithms and Experiments (ALEX’98), R. Battini, A. A. Bertossi (Hrsg.) (1998). 165–174.
- [ Abstract ]
- [ BibTeX ]
MakeIt! automizes the process of writing makefiles for C and C++ projects. MakeIt! supports the idea of literate programming, i.e. of keeping code and documentation in one file. From this file, a LaTeX file with the documentation and product files with the program code are extracted. All implementation files are then scanned for include statements in order to detect dependencies among them. These are written into so-called dependency files and subsequently used by the make process to ensure that products and documentation are up to date. The time overhead is small since a dependency file contains only the dependencies deduced from one file. Thus it can be reused until a change in this file occurs. par MakeIt! simplifies software development and improves the resulting software in three ways. par o MakeIt! frees the programmer's mind of the duty of writing and maintaining makefiles, par o MakeIt! simplifies (but does not depend on) the use of literate programming, and par o MakeIt! offers full support for simultaneous work on different platforms with different compilers, which is a necessity for developing portable code.

@inproceedings{sw-mgmma-98, abstract = {MakeIt! automizes the process of writing makefiles for C and C++ projects. MakeIt! supports the idea of literate programming, i.e. of keeping code and documentation in one file. From this file, a LaTeX file with the documentation and product files with the program code are extracted. All implementation files are then scanned for include statements in order to detect dependencies among them. These are written into so-called dependency files and subsequently used by the make process to ensure that products and documentation are up to date. The time overhead is small since a dependency file contains only the dependencies deduced from one file. Thus it can be reused until a change in this file occurs. \par MakeIt! simplifies software development and improves the resulting software in three ways. \par o MakeIt! frees the programmer's mind of the duty of writing and maintaining makefiles, \par o MakeIt! simplifies (but does not depend on) the use of literate programming, and \par o MakeIt! offers full support for simultaneous work on different platforms with different compilers, which is a necessity for developing portable code.}, address = {Trento}, author = {Sch{\"o}nherr, Sven and Wolff, Alexander}, booktitle = {Proc. Workshop on Algorithms and Experiments (ALEX'98)}, editor = {Battini, Roberto and Bertossi, Alan A.}, keywords = {myown}, pages = {165–174}, title = {MakeIt! – {Generating} and Maintaining Makefiles Automatically}, year = 1998 }
Fast and Reliable Map Labeling Wagner, Frank; Wolff, Alexander in Proc. 9th Int. Symp. Computer Science for Environment Protection (CSEP’95), H. K. und Werner Pillmann (Hrsg.) (1995). 667–675.
- [ BibTeX ]
@inproceedings{ww-frml-95, author = {Wagner, Frank and Wolff, Alexander}, booktitle = {Proc. 9th Int. Symp. Computer Science for Environment Protection (CSEP'95)}, editor = {und Werner Pillmann, Horst Kremers}, keywords = {myown}, pages = {667–675}, publisher = {Metropolis}, title = {Fast and Reliable Map Labeling}, year = 1995 }
An Efficient and Effective Approximation Algorithm for the Map Labeling Problem Wagner, Frank; Wolff, Alexander in Proc. 3rd Annu. Europ. Symp. on Algorithms (ESA’95), Lecture Notes in Computer Science, P. Spirakis (Hrsg.) (1995). (Bd. 979) 420–433.
- [ BibTeX ]
- [ DOI ]
@inproceedings{ww-eeaam-95, author = {Wagner, Frank and Wolff, Alexander}, booktitle = {Proc. 3rd Annu. Europ. Symp. on Algorithms (ESA'95)}, editor = {Spirakis, Paul}, keywords = {myown}, pages = {420–433}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {An Efficient and Effective Approximation Algorithm for the Map Labeling Problem}, volume = 979, year = 1995 }
Map Labeling Heuristics: Provably Good and Practically Useful Wagner, Frank; Wolff, Alexander in Proc. 11th Annu. ACM Sympos. Comput. Geom. (SoCG’95) (1995). 109–118.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
@inproceedings{ww-mlhpg-95, author = {Wagner, Frank and Wolff, Alexander}, booktitle = {Proc. 11th Annu. ACM Sympos. Comput. Geom. (SoCG'95)}, keywords = {myown}, pages = {109–118}, title = {Map Labeling Heuristics: Provably Good and Practically Useful}, year = 1995 }

Mastersthesis[ to top ]

Map Labeling Wolff, Alexander PhD thesis, Fachbereich Mathematik und Informatik, Freie Universität Berlin. (1995, Mai).
- [ BibTeX ]
@mastersthesis{w-ml-95, author = {Wolff, Alexander}, keywords = {myown}, month = {may}, school = {Fachbereich Mathematik und Informatik, Freie Universit{\"a}t Berlin}, title = {Map Labeling}, year = 1995 }

Misc[ to top ]

Survey on Graph and Hypergraph Drawing Schulz, André; Wolff, Alexander (M. Löffler; A. Lubiw; S. Schleimer; E. M. W. Chambers, Hrsg.) (2019). 87–89.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
@misc{sw-sghd-DR19, author = {Schulz, Andr{\'e} and Wolff, Alexander}, booktitle = {Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)}, editor = {L{\"o}ffler, Maarten and Lubiw, Anna and Schleimer, Saul and Chambers, Erin Moriarty Wolf}, keywords = {myown}, pages = {87–89}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {Dagstuhl Reports}, title = {Survey on Graph and Hypergraph Drawing}, volume = {9 (number 8)}, year = 2019 }
Geometrische Netzwerke und ihre Visualisierung Wolff, Alexander (2005, Juni).
- [ BibTeX ]
- [ pdf ]
@misc{w-gniv-05, author = {Wolff, Alexander}, howpublished = {Habilitationsschrift (kumulativ), Fakult{\"a}t f{\"u}r Informatik, Universit{\"a}t Karlsruhe}, keywords = {myown}, month = {jun}, school = {Fakult{\"a}t f{\"u}r Informatik, Universit{\"a}t Karlsruhe}, title = {{Geometrische Netzwerke und ihre Visualisierung}}, year = 2005 }
The Map-Labeling Bibliography Wolff, Alexander; Strijk, Tycho (1996).
- [ BibTeX ]
- [ URL ]
@misc{ws-mlb-96, author = {Wolff, Alexander and Strijk, Tycho}, howpublished = {\url{http://i11www.ira.uka.de/map-labeling/bibliography}}, keywords = {myown}, title = {The {M}ap-{L}abeling {B}ibliography}, year = 1996 }

PhD thesis[ to top ]

Automated Label Placement in Theory and Practice Wolff, Alexander PhD thesis, Fachbereich Mathematik und Informatik, Freie Universität Berlin. (1999, Mai).
- [ BibTeX ]
- [ pdf ]
@phdthesis{w-alptp-99, author = {Wolff, Alexander}, keywords = {myown}, month = {may}, school = {Fachbereich Mathematik und Informatik, Freie Universit{\"a}t Berlin}, title = {Automated Label Placement in Theory and Practice}, type = {PhD thesis}, year = 1999 }

Proceedings[ to top ]

Visual Analytics for Sets over Time and Space Fabrikant, Sara Irina; Miksch, Silvia; Wolff, Alexander (2019). (Bd. 9) 31–57. Schloss Dagstuhl~-- Leibniz-Zentrum für Informatik.
- [ BibTeX ]
- [ DOI ]
@proceedings{fmw-vasts-DR19, annote = {Keywords: Geovisualization, graph drawing, information visualization, set visualization, visual analytics}, editor = {Fabrikant, Sara Irina and Miksch, Silvia and Wolff, Alexander}, journal = {Dagstuhl Reports}, keywords = {myown}, note = {Dagstuhl Seminar 19192}, number = 5, pages = {31–57}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, title = {Visual Analytics for Sets over Time and Space}, volume = 9, year = 2019 }
Proceedings of the 21st International Symposium on Graph Drawing (GD’13) Wismath, Stephen; Wolff, Alexander in Lecture Notes in Computer Science (2013). (Bd. 8242) Springer-Verlag.
- [ BibTeX ]
- [ DOI ]
@proceedings{ww-21isgd-GD13, editor = {Wismath, Stephen and Wolff, Alexander}, keywords = {myown}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {{Proceedings of the 21st International Symposium on Graph Drawing (GD'13)}}, volume = 8242, year = 2013 }
Putting Data on the Map Kobourov, Stephen; Wolff, Alexander; van Ham, Frank in Dagstuhl Reports (2012). (Bd. 2) 51–76. Schloss Dagstuhl~-- Leibniz-Zentrum für Informatik.
- [ BibTeX ]
- [ DOI ]
@proceedings{kwh-pdm-DR12, annote = {Keywords: Information Visualization, Cartography, GIScience, Computational Geometry, Graph Drawing, Cognition}, editor = {Kobourov, Stephen and Wolff, Alexander and van Ham, Frank}, keywords = {myown}, note = {Dagstuhl Seminar 12261}, number = 6, pages = {51–76}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {Dagstuhl Reports}, title = {Putting Data on the Map}, volume = 2, year = 2012 }
Schematization in Cartography, Visualization, and Computational Geometry Dykes, Jason; Müller-Hannemann, Matthias; Wolff, Alexander in Dagstuhl Seminar Proceedings (2011). (Bd. 10461) Schloss Dagstuhl~-- Leibniz-Zentrum für Informatik.
- [ BibTeX ]
- [ URL ]
@proceedings{dmw-scvcg-11, editor = {Dykes, Jason and M{\"u}ller-Hannemann, Matthias and Wolff, Alexander}, keywords = {underground_mining}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {Dagstuhl Seminar Proceedings}, title = {Schematization in Cartography, Visualization, and Computational Geometry}, volume = 10461, year = 2011 }
Geometric Networks and Metric Space Embeddings Gudmundsson, Joachim; Klein, Rolf; Narasimhan, Giri; Smid, Michiel; Wolff, Alexander in Dagstuhl Seminar Proceedings (2007). (Bd. 06481) Schloss Dagstuhl~-- Leibniz-Zentrum für Informatik.
- [ BibTeX ]
- [ URL ]
- [ pdf ]
@proceedings{gknsw-gnmse-07, editor = {Gudmundsson, Joachim and Klein, Rolf and Narasimhan, Giri and Smid, Michiel and Wolff, Alexander}, keywords = {spanners}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {Dagstuhl Seminar Proceedings}, title = {Geometric Networks and Metric Space Embeddings}, volume = {06481}, year = 2007 }

Nach oben

Veröffentlichungen (nach Typ)

Hinweis zum Datenschutz

Hinweis zum Datenschutz

Bildnachweise