Publications (chronologically)

[ 2024 ]
[ 2023 ]
[ 2022 ]
[ 2021 ]
[ 2020 ]
[ 2019 ]
[ 2018 ]
[ 2017 ]
[ 2016 ]
[ 2015 ]
[ 2014 ]
[ 2013 ]
[ 2012 ]
[ 2011 ]
[ 2010 ]
[ 2009 ]
[ 2008 ]
[ 2007 ]
[ 2006 ]
[ 2005 ]
[ 2004 ]
[ 2003 ]
[ 2002 ]
[ 2001 ]
[ 2000 ]
[ 1999 ]
[ 1998 ]
[ 1997 ]
[ 1996 ]
[ 1995 ]

2024[ to top ]

Eliminating Crossings in Ordered Graphs. Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. In Proc. 19th Scand. Symp. Algorithm Theory (SWAT’24), Vol. 294 of LIPIcs, H. Bodlaender (ed.), pp. 1:1–19. Schloss Dagstuhl – Leibniz-Institut für Informatik, 2024.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{ackssuw-ecog-SWAT24, author = {Agrawal, Akanksha and Cabello, Sergio and Kaufmann, Michael and Saurabh, Saket and Sharma, Roohani and Uno, Yushi and Wolff, Alexander}, booktitle = {Proc. 19th Scand. Symp. Algorithm Theory (SWAT'24)}, editor = {Bodlaender, Hans}, keywords = {hitting_set}, pages = {1:1–19}, publisher = {Schloss Dagstuhl – Leibniz-Institut für Informatik}, series = {LIPIcs}, title = {Eliminating Crossings in Ordered Graphs}, volume = 294, year = 2024 }
Constrained and Ordered Level Planarity Parameterized by the Number of Levels. Vacláv Blažej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. In Proc. 40th Annu. Sympos. Comput. Geom. (SoCG’24), Vol. 293 of LIPIcs, W. Mulzer, J. M. Phillips (eds.), pp. 21:1–16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{bkkswz-colpp-SoCG24, author = {Blažej, Vacláv and Klemz, Boris and Klesen, Felix and Sieper, Marie Diana and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 40th Annu. Sympos. Comput. Geom. (SoCG'24)}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, keywords = {level_planarity}, pages = {21:1–16}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {LIPIcs}, title = {Constrained and Ordered Level Planarity Parameterized by the Number of Levels}, volume = 293, year = 2024 }
Adjacency Graphs of Polyhedral Surfaces. Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Discrete & Computational Geometry, 71, pp. 1429–1455. 2024.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in~$$\mathbb{R}^3$$. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $$K_5$$, $$K_{5,81}$$, or any nonplanar $$3$$-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $$K_{4,4}$$, and $$K_{3,5}$$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al.~(1983), for any hypercube. par Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable $$n$$-vertex graphs is in $$\Omega(n \log n)$$. From the non-realizability of $$K_{5,81}$$, we obtain that any realizable $$n$$-vertex graph has $$\bigO(n^{9/5})$$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.

@article{akklsvw-dgps-DCG24, abstract = {We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $\mathbb{R}^3$. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $K_5$, $K_{5,81}$, or any nonplanar $3$-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $K_{4,4}$, and $K_{3,5}$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. \par Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable $n$-vertex graphs is in $\Omega(n \log n)$. From the non-realizability of $K_{5,81}$, we obtain that any realizable $n$-vertex graph has $\bigO(n^{9/5})$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.}, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and Löffler, Maarten and Schulz, André and Vogtenhuber, Birgit and Wolff, Alexander}, journal = {Discrete \& Computational Geometry}, keywords = {realizability}, pages = {1429–1455}, title = {Adjacency Graphs of Polyhedral Surfaces}, volume = 71, year = 2024 }
Morphing Graph Drawings in the Presence of Point Obstacles. Oksana Firman, Tim Hegemann, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. In Proc. 50th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’24), Vol. 14519 of Lecture Notes in Computer Science, H. Fernau, S. Gaspers, R. Klasing (eds.), pp. 240–254. Springer-Verlag, 2024.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{fhkkswz-mgdppo-SOFSEM24, author = {Firman, Oksana and Hegemann, Tim and Klemz, Boris and Klesen, Felix and Sieper, Marie Diana and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 50th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'24)}, editor = {Fernau, Henning and Gaspers, Serge and Klasing, Ralf}, keywords = {myown}, pages = {240–254}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Morphing Graph Drawings in the Presence of Point Obstacles}, volume = 14519, year = 2024 }
Outerplanar and Forest Storyplans. Jiří Fiala, Oksana Firman, Giuseppe Liotta, Alexander Wolff, and Johannes Zink. In Proc. 50th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’24), Vol. 14519 of Lecture Notes in Computer Science, H. Fernau, S. Gaspers, R. Klasing (eds.), pp. 211–225. Springer-Verlag, 2024.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{fflwz-ofs-SOFSEM24, author = {Fiala, Jiří and Firman, Oksana and Liotta, Giuseppe and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 50th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'24)}, editor = {Fernau, Henning and Gaspers, Serge and Klasing, Ralf}, keywords = {myown}, pages = {211–225}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Outerplanar and Forest Storyplans}, volume = 14519, year = 2024 }
Bounding and Computing Obstacle Numbers of Graphs. Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff. SIAM J. Discrete Math., 38(2), pp. 1537–1565. 2024.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. par It is known that the obstacle number of each n-vertex graph is O(n log n) [Balko, Cibulka, and Valtr, 2018] and that there are n-vertex graphs whose obstacle number is Ω(n/(log log n)^2) [Dujmović and Morin, 2015]. We improve this lower bound to Ω(n/log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n2) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. par We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle.

@article{bcghvw-bcong-SIDMA24, abstract = {An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. \par It is known that the obstacle number of each n-vertex graph is O(n log n) [Balko, Cibulka, and Valtr, 2018] and that there are n-vertex graphs whose obstacle number is Ω(n/(log log n)^2) [Dujmović and Morin, 2015]. We improve this lower bound to Ω(n/log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n2) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. \par We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle.}, author = {Balko, Martin and Chaplick, Steven and Ganian, Robert and Gupta, Siddharth and Hoffmann, Michael and Valtr, Pavel and Wolff, Alexander}, journal = {SIAM J. Discrete Math.}, keywords = {convex_obstacle_number}, number = 2, pages = {1537–1565}, title = {Bounding and Computing Obstacle Numbers of Graphs}, volume = 38, year = 2024 }

2023[ to top ]

Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees. Jonathan Klawitter, Felix Klesen, Moritz Niederer, and Alexander Wolff. In Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Vol. 13878 of Lecture Notes in Computer Science, L. Gąsieniec (ed.), pp. 96–110. Springer-Verlag, 2023.
- [ 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ą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 }
Parameterized Approaches to Orthogonal Compaction. Walter Didimo, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Alexander Wolff, and Meirav Zehavi. In Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Vol. 13878 of Lecture Notes in Computer Science, L. Gąsieniec (ed.), pp. 111–128. Springer-Verlag, 2023.
- [ 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ą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. Kevin Buchin, Will Evans, Fabrizio Frati, Irina Kostitsyna, Maarten Löffler, Tim Ophelders, and Alexander Wolff. In Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Vol. 13878 of Lecture Notes in Computer Science, L. Gąsieniec (ed.), pp. 80–95. Springer-Verlag, 2023.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{befklow-mpgdt3d-SOFSEM23, author = {Buchin, Kevin and Evans, Will and Frati, Fabrizio and Kostitsyna, Irina and Löffler, Maarten and Ophelders, Tim and Wolff, Alexander}, booktitle = {Proc. 49th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'23)}, editor = {Gą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 }
The Complexity of Finding Tangles. Oksana Firman, Philipp Kindermann, Boris Klemz, Alexander Ravsky, Alexander Wolff, and Johannes Zink. In Proc. 49th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’23), Vol. 13878 of Lecture Notes in Computer Science, L. Gąsieniec (ed.), pp. 3–17. Springer-Verlag, 2023.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{fkkrwz-cotf-SOFSEM23, author = {Firman, Oksana and Kindermann, Philipp and Klemz, Boris and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 49th Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'23)}, editor = {Gą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 }
Planar L-Drawings of Directed Graphs. Steven Chaplick, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Martin Nöllenburg, Maurizio Patrignani, Ioannis G. Tollis, and Alexander Wolff. Computing in Geometry and Topology, 2(1), pp. 7:1–7:15. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
In this paper, we study drawings of directed graphs. We use the L-drawing standard where each edge is represented by a polygonal chain that consists of a vertical line segment incident to the source of the edge and a horizontal line segment incident to the target. par First, we consider planar L-drawings. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. We also show how to decide in linear time whether there exists a planar L-drawing of a plane directed graph with a fixed assignment of the edges to the four sides (top, bottom, left, and right) of the vertices. par Second, we consider upward- (resp.\ upward-rightward-) planar L-drawings. We provide upper bounds on the maximum number of edges of graphs admitting such drawings. Moreover, we characterize the directed st-graphs admitting an upward- (resp.\ upward-rightward-) planar L-drawing as exactly those admitting an embedding supporting a bitonic (resp.\ monotonically decreasing) st-ordering.

@article{cccdnptw-plddg-JGAA23, abstract = {In this paper, we study drawings of directed graphs. We use the L-drawing standard where each edge is represented by a polygonal chain that consists of a vertical line segment incident to the source of the edge and a horizontal line segment incident to the target. \par First, we consider planar L-drawings. We provide necessary conditions for the existence of these drawings and show that testing for the existence of a planar L-drawing is an NP-complete problem. We also show how to decide in linear time whether there exists a planar L-drawing of a plane directed graph with a fixed assignment of the edges to the four sides (top, bottom, left, and right) of the vertices. \par Second, we consider upward- (resp.\ upward-rightward-) planar L-drawings. We provide upper bounds on the maximum number of edges of graphs admitting such drawings. Moreover, we characterize the directed st-graphs admitting an upward- (resp.\ upward-rightward-) planar L-drawing as exactly those admitting an embedding supporting a bitonic (resp.\ monotonically decreasing) st-ordering.}, author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and {Da Lozzo}, Giordano and Nöllenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander}, journal = {Computing in Geometry and Topology}, keywords = {bitonic_st-ordering}, number = 1, pages = {7:1–7:15}, title = {Planar {L}-Drawings of Directed Graphs}, volume = 2, year = 2023 }
Morphing Rectangular Duals. Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter, and Alexander Wolff. In Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD’22), Vol. 13764 of Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (eds.), pp. 389–403. Springer-Verlag, 2023.
- [ 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 = 2023 }
Morphing Planar Graph Drawings Through 3D. Kevin Buchin, Will Evans, Fabrizio Frati, Irina Kostitsyna, Maarten Löffler, Tim Ophelders, and Alexander Wolff. Computing in Geometry and Topology, 2(1), pp. 5:1–5:18. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-line drawings of an $$n$$-vertex planar graph, there exists a piecewise-linear crossing-free 3D morph with $$O(n^2)$$ steps that transforms one drawing into the other. We also give some evidence why it is difficult to obtain a linear lower bound (which exists in 2D) for the number of steps of a crossing-free 3D morph.

@article{befklow-mpgdt3d-CGT23, abstract = {In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-line drawings of an $n$-vertex planar graph, there exists a piecewise-linear crossing-free 3D morph with $O(n^2)$ steps that transforms one drawing into the other. We also give some evidence why it is difficult to obtain a linear lower bound (which exists in 2D) for the number of steps of a crossing-free 3D morph.}, author = {Buchin, Kevin and Evans, Will and Frati, Fabrizio and Kostitsyna, Irina and Löffler, Maarten and Ophelders, Tim and Wolff, Alexander}, journal = {Computing in Geometry and Topology}, keywords = {morphing}, number = 1, pages = {5:1–5:18}, title = {Morphing Planar Graph Drawings Through {3D}}, volume = 2, year = 2023 }
Coloring Mixed and Directional Interval Graphs. Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter, Joachim Spoerhase, Alexander Wolff, and Johannes Zink. In Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD’22), Vol. 13764 of Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (eds.), pp. 418–431. Springer-Verlag, 2023.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{gmrswz-cmdig-GD22, author = {Gutowski, Grzegorz and Mittelstä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 = {418–431}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Coloring Mixed and Directional Interval Graphs}, volume = 13764, year = 2023 }
Outside-Obstacle Representations with All Vertices on the Outer Face. Oksana Firman, Philipp Kindermann, Jonathan Klawitter, Boris Klemz, Felix Klesen, and Alexander Wolff. In Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD’22), Vol. 13764 of Lecture Notes in Computer Science, P. Angelini, R. von Hanxleden (eds.), pp. 432–440. Springer-Verlag, 2023.
- [ 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 = {432–440}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Outside-Obstacle Representations with All Vertices on the Outer Face}, volume = 13764, year = 2023 }
Coloring and Recognizing Mixed Interval Graphs. Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. In Proc. 34th Annu. Int. Symp. Algorithms Comput. (ISAAC’23), Vol. 283 of LIPIcs, S. Iwata, N. Kakimura (eds.), pp. 36:1–14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{gjkrwz-crdig-ISAAC23, author = {Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Klesen, Felix and Rzążewski, Paweł and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 34th Annu. Int. Symp. Algorithms Comput. (ISAAC'23)}, editor = {Iwata, Satoru and Kakimura, Naonori}, keywords = {myown}, pages = {36:1–14}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {LIPIcs}, title = {Coloring and Recognizing Mixed Interval Graphs}, volume = 283, year = 2023 }
A Simple Pipeline for Orthogonal Graph Drawing. Tim Hegemann and Alexander Wolff. In Proc. 31st Int. Symp. Graph Drawing & Network Vis. (GD’23), Vol. 14466 of Lecture Notes in Computer Science, M. Bekos, M. Chimani (eds.), pp. 170–186. Springer-Verlag, 2023.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{hw-spogd-GD23, author = {Hegemann, Tim and Wolff, Alexander}, booktitle = {Proc. 31st Int. Symp. Graph Drawing \& Network Vis. (GD'23)}, editor = {Bekos, Michael and Chimani, Markus}, keywords = {myown}, pages = {170–186}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {A Simple Pipeline for Orthogonal Graph Drawing}, volume = 14466, year = 2023 }
The Parametrized Complexity of the Segment Number. Sabine Cornelsen, Giordano Da Lozzo, Luca Grilli, Siddharth Gupta, Jan Kratochvíl, and Alexander Wolff. In Proc. 31st Int. Symp. Graph Drawing & Network Vis. (GD’23), Vol. 14466 of Lecture Notes in Computer Science, M. Bekos, M. Chimani (eds.), pp. 97–113. Springer-Verlag, 2023.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{cdggkw-pcsn-GD23, author = {Cornelsen, Sabine and {Da Lozzo}, Giordano and Grilli, Luca and Gupta, Siddharth and Kratochvíl, Jan and Wolff, Alexander}, booktitle = {Proc. 31st Int. Symp. Graph Drawing \& Network Vis. (GD'23)}, editor = {Bekos, Michael and Chimani, Markus}, keywords = {myown}, pages = {97–113}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {The Parametrized Complexity of the Segment Number}, volume = 14466, year = 2023 }
The Complexity of Drawing Graphs on Few Lines and Few Planes. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff. Journal of Graph Algorithms & Applications, 27(6), pp. 459–488. 2023.
- [ BibTeX ]
- [ DOI ]
@article{cflrvw-cdgfl-JGAA23, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {myown}, number = 6, pages = {459–488}, title = {The Complexity of Drawing Graphs on Few Lines and Few Planes}, volume = 27, year = 2023 }
The Computational Complexity of the ChordLink Model. Philipp Kindermann, Jan Sauer, and Alexander Wolff. Journal of Graph Algorithms & Applications, 27(9), pp. 759–767. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
In order to visualize well-clustered graphs with many intra-cluster but few inter-cluster edges, hybrid approaches have been proposed. For example, ChordLink draws the clusters as chord diagrams and embeds these into a node-link diagram that represents the overall structure of the clustered graph. The ChordLink approach consists of four steps; node replication, node permutation, node merging, and chord insertion. In this paper, we focus on the optimization problems defined by two of these steps. We show that the decision version of the problem defined by node permutation is NP-complete and present an efficient algorithm for a special case. For chord insertion, we show that it is NP-complete to decide whether a crossing-free placement of the chords exists. Moreover, it is APX-hard to minimize the number of crossings among the chords. Our results answer an open question posed by Angori, Didimo, Montecchiani, Pagliuca, and Tappini, who introduced ChordLink [TVCG 2021].

@article{ksw-cccm-JGAA23, abstract = {In order to visualize well-clustered graphs with many intra-cluster but few inter-cluster edges, hybrid approaches have been proposed. For example, ChordLink draws the clusters as chord diagrams and embeds these into a node-link diagram that represents the overall structure of the clustered graph. The ChordLink approach consists of four steps; node replication, node permutation, node merging, and chord insertion. In this paper, we focus on the optimization problems defined by two of these steps. We show that the decision version of the problem defined by node permutation is NP-complete and present an efficient algorithm for a special case. For chord insertion, we show that it is NP-complete to decide whether a crossing-free placement of the chords exists. Moreover, it is APX-hard to minimize the number of crossings among the chords. Our results answer an open question posed by Angori, Didimo, Montecchiani, Pagliuca, and Tappini, who introduced ChordLink [TVCG 2021].}, author = {Kindermann, Philipp and Sauer, Jan and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {APX-hard}, number = 9, pages = {759–767}, title = {The Computational Complexity of the {ChordLink} Model}, volume = 27, year = 2023 }

2022[ to top ]

Minimum Rectilinear Polygons for Given Angle Sequences. William S. Evans, Krzysztof Fleszar, Philipp Kindermann, Noushin Saeedi, Chan-Su Shin, and Alexander Wolff. Computational Geometry: Theory and Applications, 100(101820), pp. 1–39. 2022.
- [ 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 }
The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs. Ina Goeßmann, Jonathan Klawitter, Boris Klemz, Felix Klesen, Stephen G. Kobourov, Myroslav Kryven, Alexander Wolff, and Johannes Zink. In Proc. 48th Int. Workshop Graph-Theoretic Concepts Comput. Sci. (WG’22), Vol. 13453 of Lecture Notes in Computer Science, M. Bekos, M. Kaufmann (eds.), p. 16 pages. Springer-Verlag, 2022.
- [ 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 }
Bounding and Computing Obstacle Numbers of Graphs. Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff. In Proc. 30th Europ. Symp. Algorithms (ESA’22), Vol. 244 of LIPIcs, S. Chechik, G. Navarro, E. Rotenberg, G. Herman (eds.), pp. 11:1–13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{bcghvw-bcong-ESA22, author = {Balko, Martin and Chaplick, Steven and Ganian, Robert 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ür Informatik}, series = {LIPIcs}, title = {Bounding and Computing Obstacle Numbers of Graphs}, volume = 244, year = 2022 }
The Computational Complexity of the ChordLink Model. Philipp Kindermann, Jan Sauer, and Alexander Wolff. In Proc. 38th Europ. Workshop Comput. Geom. (EuroCG’22), E. Di Giacomo, F. Montecchiani (eds.), pp. 10:1–7. 2022.
- [ 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 }
Layered Drawing of Undirected Graphs with Generalized Port Constraints. Johannes Zink, Julian Walter, Joachim Baumeister, and Alexander Wolff. Computational Geometry: Theory and Applications, 105--106(101886), pp. 1–29. 2022.
- [ 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 = {Sugiyama_framework}, number = 101886, pages = {1–29}, title = {Layered Drawing of Undirected Graphs with Generalized Port Constraints}, volume = {105–106}, year = 2022 }
Algorithms for Floor Planning with Proximity Requirements. Jonathan Klawitter, Felix Klesen, and Alexander Wolff. In Proc. CAAD Future 2021, Vol. 1465 of CCIS, D. J. Gerber, A. Nahmad, B. Bogosian, E. Pantazis, C. Miltiadis (eds.), pp. 151–171. Springer-Verlag, 2022.
- [ 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 }
Simple Algorithms for Partial and Simultaneous Rectangular Duals with Given Contact Orientations. Steven Chaplick, Stefan Felsner, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter, and Alexander Wolff. Theoretical Computer Science, 919, pp. 66–74. 2022.
- [ 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 = {contact_representation}, pages = {66–74}, title = {Simple Algorithms for Partial and Simultaneous Rectangular Duals with Given Contact Orientations}, volume = 919, year = 2022 }

2021[ to top ]

Adjacency Graphs of Polyhedral Surfaces. Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. In Proc. 37th Annu. Sympos. Comput. Geom. (SoCG’21), Vol. 189 of LIPIcs, K. Buchin, Éric Colin de Verdière (eds.), pp. 11:1–17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{akklsvw-dgps-SoCG21, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and Löffler, Maarten and Schulz, André and Vogtenhuber, Birgit and Wolff, Alexander}, booktitle = {Proc. 37th Annu. Sympos. Comput. Geom. (SoCG'21)}, editor = {Buchin, Kevin and {Colin de Verdière}, Éric}, keywords = {realizability}, pages = {11:1–17}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {LIPIcs}, title = {Adjacency Graphs of Polyhedral Surfaces}, volume = 189, year = 2021 }
Angle Covers: Algorithms and Complexity. William Evans, Ellen Gethner, Jack Spalding-Jamieson, and Alexander Wolff. Journal of Graph Algorithms & Applications, 25(2), pp. 643–661. 2021.
- [ 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 }
Layered Drawing of Undirected Graphs with Generalized Port Constraints. Julian Walter, Johannes Zink, Joachim Baumeister, and Alexander Wolff. In Proc. 28th Int. Symp. Graph Drawing & Network Vis. (GD’20), Vol. 12590 of Lecture Notes in Computer Science, D. Auber, P. Valtr (eds.), pp. 220–234. Springer-Verlag, 2021.
- [ 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 }
ClusterSets: Optimizing Planar Clusters in Categorical Point Data. Jakob Geiger, Sabine Cornelsen, Jan-Henrik Haunert, Philipp Kindermann, Tamara Mchedlidze, Martin Nöllenburg, Yoshio Okamoto, and Alexander Wolff. Comput. Graphics Forum, 40(3), pp. 471–481. 2021.
- [ 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ö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 }
Using the Metro-Map Metaphor for Drawing Hypergraphs. Fabian Frank, Michael Kaufmann, Stephen Kobourov, Tamara Mchedlidze, Sergey Pupyrev, Torsten Ueckerdt, and Alexander Wolff. In Proc. 47th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’21), Vol. 12607 of Lecture Notes in Computer Science, T. Bureš, R. Dondi, J. Gamper, G. Guerrini, T. Jurdziński, C. Pahl, F. Sikora, P. Wong (eds.), pp. 361–372. Springer-Verlag, 2021.
- [ 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š, Tomáš and Dondi, Riccardo and Gamper, Johann and Guerrini, Giovanna and Jurdziń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 }
Extending Partial Representations of Rectangular Duals with Given Contact Orientations. Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter, and Alexander Wolff. In Proc. 12th International Conference on Algorithms and Complexity (CIAC’21), Vol. 12701 of Lecture Notes in Computer Science, T. Calamoneri, F. Coró (eds.), pp. 340–353. Springer-Verlag, 2021.
- [ 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ó, 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 }

2020[ to top ]

Stick Graphs with and without Length Constraints. Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele, Alexander Wolff, Alexander Zaft, and Johannes Zink. Journal of Graph Algorithms & Applications, 24(4), pp. 657–681. 2020.
- [ 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ö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 with Circular Arcs and Right-Angle Crossings. Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. In Proc. 17th Scand. Symp. and Workshops on Algorithm Theory (SWAT’20), Vol. 162 of LIPIcs, S. Albers (ed.), pp. 21:1–14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{cfkw-dgcar-SWAT20, author = {Chaplick, Steven and Förster, Henry and Kryven, Myroslav and Wolff, Alexander}, booktitle = {Proc. 17th Scand. Symp. and Workshops on Algorithm Theory (SWAT'20)}, editor = {Albers, Susanne}, keywords = {charging_argument}, pages = {21:1–14}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {LIPIcs}, title = {Drawing Graphs with Circular Arcs and Right-Angle Crossings}, volume = 162, year = 2020 }
Drawing Graphs on Few Lines and Few Planes. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff. Journal of Computational Geometry, 11(1), pp. 433–475. 2020.
- [ 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 = {affine_cover_number}, number = 1, pages = {433–475}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 11, year = 2020 }
Finding Optimal Sequences for Area Aggregation---A* vs. Integer Linear Programming. Dongliang Peng, Alexander Wolff, and Jan-Henrik Haunert. ACM Transactions on Spatial Algorithms and Systems, 7(1). 2020.

article 4 (40 pages)
- [ 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 = {land_cover}, note = {article 4 (40 pages)}, number = 1, title = {Finding Optimal Sequences for Area Aggregation—{A}* vs.\ Integer Linear Programming}, volume = 7, year = 2020 }
Angle Covers: Algorithms and Complexity. William Evans, Ellen Gethner, Jack Spalding-Jamieson, and Alexander Wolff. In Proc. 14th Int. Workshop Algorithms Comput. (WALCOM’20), Vol. 12049 of Lecture Notes in Computer Science, S. Rahman, K. Sadakane, W.-K. Sung (eds.), pp. 94–106. Springer-Verlag, 2020.
- [ 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 }
Bundled Crossings Revisited. Steven Chaplick, Thomas C. van Dijk, Myroslav Kryven, Ji-Won Park, Alexander Ravsky, and Alexander Wolff. Journal of Graph Algorithms & Applications, 24(4), pp. 621–655. 2020.
- [ 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 = {fixed-parameter_tractable}, number = 4, pages = {621–655}, title = {Bundled Crossings Revisited}, volume = 24, year = 2020 }

2019[ to top ]

Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. Computational Geometry: Theory and Applications, 84, pp. 50–68. 2019.

Special Issue on the 34th European Workshop on Computational Geometry
- [ 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 = {gd-info1}, 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 }
Computing Optimal-Height Tangles Faster. Oksana Firman, Philipp Kindermann, Alexander Ravsky, Alexander Wolff, and Johannes Zink. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 203–215. Springer-Verlag, 2019.
- [ 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óth, Csaba D.}, keywords = {gd-info1}, pages = {203–215}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Computing Optimal-Height Tangles Faster}, volume = 11904, year = 2019 }
Representing Graphs and Hypergraphs by Touching Polygons in 3D. William Evans, Paweł Rzążewski, Noushin Saeedi, Chan-Su Shin, and Alexander Wolff. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 18–32. Springer-Verlag, 2019.

http://arxiv.org/abs/1908.08273
- [ BibTeX ]
- [ DOI ]
- [ slides ]
@inproceedings{erssw-rghtp-GD19, author = {Evans, William and Rzążewski, Paweł 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ó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 }
Variants of the Segment Number of a Graph. Yoshio Okamoto, Alexander Ravsky, and Alexander Wolff. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 430–443. Springer-Verlag, 2019.
- [ 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ó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 }
Stick Graphs with Length Constraints. Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele, Alexander Wolff, Alexander Zaft, and Johannes Zink. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 3–17. Springer-Verlag, 2019.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{ckltwzz-sglc-GD19, author = {Chaplick, Steven and Kindermann, Philipp and Lö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óth, Csaba D.}, keywords = {gd-info1}, pages = {3–17}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Stick Graphs with Length Constraints}, volume = 11904, year = 2019 }
Survey on Graph and Hypergraph Drawing. André Schulz and Alexander Wolff. M. Löffler; A. Lubiw; S. Schleimer; E. M. W. Chambers (eds.), pp. 87–89. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
@misc{sw-sghd-DR19, author = {Schulz, André and Wolff, Alexander}, booktitle = {Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)}, editor = {Löffler, Maarten and Lubiw, Anna and Schleimer, Saul and Chambers, Erin Moriarty Wolf}, keywords = {Geometric_topology}, pages = {87–89}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {Dagstuhl Reports}, title = {Survey on Graph and Hypergraph Drawing}, volume = {9 (number 8)}, year = 2019 }
On Arrangements of Orthogonal Circles. Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 216–229. Springer-Verlag, 2019.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{cfkw-aoc-GD19, author = {Chaplick, Steven and Förster, Henry and Kryven, Myroslav and Wolff, Alexander}, booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)}, editor = {Archambault, Daniel and Tó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 }
Line and Plane Cover Numbers Revisited. Therese Biedl, Stefan Felsner, Henk Meijer, and Alexander Wolff. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 409–415. Springer-Verlag, 2019.
- [ 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ó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 }
Drawing Graphs on Few Circles and Few Spheres. Myroslav Kryven, Alexander Ravsky, and Alexander Wolff. Journal of Graph Algorithms & Applications, 23(2), pp. 371–391. 2019.
- [ 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 = {gd-info1}, number = 2, pages = {371–391}, title = {Drawing Graphs on Few Circles and Few Spheres}, volume = 23, year = 2019 }
Bundled Crossings Revisited. Steven Chaplick, Thomas C. van Dijk, Myroslav Kryven, Ji-Won Park, Alexander Ravsky, and Alexander Wolff. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 63–77. Springer-Verlag, 2019.
- [ 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ó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 }
Visual Analytics for Sets over Time and Space. Sara Irina Fabrikant, Silvia Miksch, and Alexander Wolff. In Vol. 9, pp. 31–57. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.

Dagstuhl Seminar 19192
- [ 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ür Informatik}, title = {Visual Analytics for Sets over Time and Space}, volume = 9, year = 2019 }

2018[ to top ]

Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity. Evmorfia Argyriou, Sabine Cornelsen, Henry Förster, Michael Kaufmann, Martin Nöllenburg, Yoshio Okamoto, Chrysanthi Raftopoulou, and Alexander Wolff. In Proc. 26th Int. Symp. Graph Drawing & Network Vis. (GD’18), Vol. 11282 of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.), pp. 509–523. Springer-Verlag, 2018.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{acfknorw-osol1-GD18, author = {Argyriou, Evmorfia and Cornelsen, Sabine and Förster, Henry and Kaufmann, Michael and Nö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 = {gd-info1}, 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 }
Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity. Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff. In Proc. 29th Annu. Int. Symp. Algorithms Comput. (ISAAC’18), Vol. 123 of LIPIcs, W.-L. Hsu, D.-T. Lee, C.-S. Liao (eds.), pp. 61:1–13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
- [ 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ür Informatik}, series = {LIPIcs}, title = {Stabbing Rectangles by Line Segments – {How} Decomposition Reduces the Shallow-Cell Complexity}, volume = 123, year = 2018 }
On the Maximum Crossing Number. Markus Chimani, Stefan Felsner, Stephen Kobourov, Torsten Ueckerdt, Pavel Valtr, and Alexander Wolff. Journal of Graph Algorithms & Applications, 22(1), pp. 67–87. 2018.

Special issue on ``Graph Drawing Beyond Planarity''.
- [ 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 = {gd-info1}, note = {Special issue on ``Graph Drawing Beyond Planarity''.}, number = 1, pages = {67–87}, title = {On the Maximum Crossing Number}, volume = 22, year = 2018 }
Approximating the Generalized Minimum Manhattan Network Problem. Aparna Das, Krzysztof Fleszar, Stephen G. Kobourov, Joachim Spoerhase, Sankar Veeramoni, and Alexander Wolff. Algorithmica, 80(4), pp. 1170–1190. 2018.
- [ 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 = {Minimum_Manhattan_Network}, number = 4, pages = {1170–1190}, title = {Approximating the Generalized Minimum {Manhattan} Network Problem}, volume = 80, year = 2018 }
Computing Storylines with Few Block Crossings. Thomas C. van Dijk, Fabian Lipp, Peter Markfelder, and Alexander Wolff. In Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 365–378. Springer-Verlag, 2018.
- [ 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 = {gd-info1}, pages = {365–378}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Computing Storylines with Few Block Crossings}, volume = 10692, year = 2018 }
Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. In Proc. 26th Int. Symp. Graph Drawing & Network Vis. (GD’18), Vol. 11282 of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.), pp. 137–151. Springer-Verlag, 2018.
- [ 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 = {gd-info1}, 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 }
Beyond Outerplanarity. Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler, and Alexander Wolff. In Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 546–559. Springer-Verlag, 2018.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{ckllw-bo-GD17, author = {Chaplick, Steven and Kryven, Myroslav and Liotta, Giuseppe and Löffler, Andre and Wolff, Alexander}, booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {gd-info1}, pages = {546–559}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Beyond Outerplanarity}, volume = 10692, year = 2018 }
On the Maximum Crossing Number. Markus Chimani, Stefan Felsner, Stephen Kobourov, Torsten Ueckerdt, Pavel Valtr, and Alexander Wolff. In Proc. 28th Int. Workshop Combin. Algorithms (IWOCA’17), Vol. 10765 of Lecture Notes in Computer Science, L. Brankovic, J. Ryan, B. Smith (eds.), pp. 61–74. Springer-Verlag, 2018.
- [ 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 = {61–74}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {On the Maximum Crossing Number}, volume = 10765, year = 2018 }
Multi-Level Steiner Trees. Abu Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. In Proc. 17th Int. Symp. Exper. Algorithms (SEA’18), Vol. 103 of LIPIcs, G. D’Angelo (ed.), pp. 15:1–14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
- [ 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ür Informatik}, series = {LIPIcs}, title = {Multi-Level Steiner Trees}, volume = 103, year = 2018 }
Planar L-Drawings of Directed Graphs. Steven Chaplick, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Martin Nöllenburg, Maurizio Patrignani, Ioannis G. Tollis, and Alexander Wolff. In Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 465–478. Springer-Verlag, 2018.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{cccdnptw-plddg-GD17, author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and {Da Lozzo}, Giordano and Nö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 = {gd-info1}, pages = {465–478}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Planar {L}-Drawings of Directed Graphs}, volume = 10692, year = 2018 }
On the Weak Line Cover Numbers. Oksana Firman, Alexander Ravsky, and Alexander Wolff. In Proc. 34th Europ. Workshop Comput. Geom. (EuroCG’18), M. Korman, W. Mulzer (eds.), pp. 63:1–5. 2018.
- [ BibTeX ]
- [ URL ]
- [ slides ]
@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 }
Drawing Graphs on Few Circles and Few Spheres. Myroslav Kryven, Alexander Ravsky, and Alexander Wolff. In Proc. 4th Conf. Algorithms & Discrete Appl. Math. (CALDAM’18), Vol. 10743 of Lecture Notes in Computer Science, B. S. Panda, P. P. Goswami (eds.), pp. 164–178. Springer-Verlag, 2018.

Best presentation award for Myroslav Kryven.
- [ 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 }

2017[ to top ]

Algorithmically-Guided User Interaction. Thomas C. van Dijk and Alexander Wolff. In Proc. 25th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’17), E. Hoel, S. D. Newsam, S. Ravada, R. Tamassia, G. Trajcevski (eds.), pp. 11:1–4. 2017.
- [ 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 }
Block Crossings in Storyline Visualizations. Thomas C. van Dijk, Martin Fink, Norbert Fischer, Fabian Lipp, Peter Markfelder, Alexander Ravsky, Subhash Suri, and Alexander Wolff. Journal of Graph Algorithms & Applications, 21(5), pp. 873–913. 2017.

Conference version received \textbf{best paper award (track A) at GD'16.
- [ 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 = {FPT}, 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 }
The Complexity of Drawing Graphs on Few Lines and Few Planes. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff. In Proc. Algorithms Data Struct. Symp. (WADS’17), Vol. 10389 of Lecture Notes in Computer Science, F. Ellen, A. Kolokolova, J.-R. Sack (eds.), pp. 265–276. Springer-Verlag, 2017.
- [ 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örg-Rü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 }
Beyond Maximum Independent Set: An Extended Integer Programming Formulation for Point Labeling. Jan-Henrik Haunert and Alexander Wolff. International Journal of Geo-Information, 6(11), p. article 342, 20 pages. 2017.
- [ 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. Till Bruckdorfer, Sabine Cornelsen, Carsten Gutwenger, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg, and Alexander Wolff. Journal of Graph Algorithms & Applications, 21(4), pp. 757–786. 2017.
- [ 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öllenburg, Martin and Wolff, Alexander}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {maximum_total_stub_length}, number = 4, pages = {757–786}, title = {Progress on Partial Edge Drawings}, volume = 21, year = 2017 }
Using the A* Algorithm to Find Optimal Sequences for Area Aggregation. Dongliang Peng, Alexander Wolff, and Jan-Henrik Haunert. In Proc. 28th Int. Cartogr. Conf. (ICC’17) -- Advances in Cartogr. & GIScience, of Lect. Notes Geoinform. Cartogr., M. P. Peterson (ed.), pp. 389–404. Springer-Verlag, 2017.
- [ 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 = {land_cover}, 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 }
Improved Approximation Algorithms for Box Contact Representations. Michael A. Bekos, Thomas C. van Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff. Algorithmica, 77(3), pp. 902–920. 2017.
- [ 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 = {Word_clouds}, number = 3, pages = {902–920}, title = {Improved Approximation Algorithms for Box Contact Representations}, volume = 77, year = 2017 }

2016[ to top ]

Snapping Graph Drawings to the Grid Optimally. Andre Löffler, Thomas C. van Dijk, and Alexander Wolff. In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.), pp. 144–151. Springer-Verlag, 2016.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{ldw-sgdgo-GD16, author = {Lö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öllenburg, Martin}, keywords = {gd-info1}, pages = {144–151}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Snapping Graph Drawings to the Grid Optimally}, volume = 9801, year = 2016 }
Beyond Maximum Independent Set: An Extended Model for Point-Feature Label Placement. Jan-Henrik Haunert and Alexander Wolff. In Proc. ISPRS (Commission II, WG II/2), Vol. XLI-B2, pp. 109–114. 2016.
- [ 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 }
Räumliche Analyse durch kombinatorische Optimierung. Jan-Henrik Haunert and Alexander Wolff. In Handbuch der Geodäsie (6 Bände), W. Freeden, R. Rummel (eds.), pp. 1–39. Springer Berlin Heidelberg, 2016.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@incollection{hw-rako-HG16, author = {Haunert, Jan-Henrik and Wolff, Alexander}, booktitle = {Handbuch der Geodäsie (6 Bände)}, editor = {Freeden, Willi and Rummel, Reiner}, keywords = {myown}, pages = {1–39}, publisher = {Springer Berlin Heidelberg}, title = {{Räumliche Analyse durch kombinatorische Optimierung}}, year = 2016 }
Minimum Rectilinear Polygons for Given Angle Sequences. William S. Evans, Krzysztof Fleszar, Philipp Kindermann, Noushin Saeedi, Chan-Su Shin, and Alexander Wolff. In Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG’16), Vol. 9943 of Lecture Notes in Computer Science, J. Akiyama, H. Ito, T. Sakai (eds.), pp. 105–119. Springer-Verlag, 2016.
- [ 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 }
Drawing Graphs on Few Lines and Few Planes. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky, and Alexander Wolff. In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.), pp. 166–180. Springer-Verlag, 2016.
- [ 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öllenburg, Martin}, keywords = {affine_cover_number}, 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 }
Multi-Sided Boundary Labeling. Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, and Alexander Wolff. Algorithmica, 76(1), pp. 225–258. 2016.
- [ 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é and Wolff, Alexander}, journal = {Algorithmica}, keywords = {dynamic_programming}, number = 1, pages = {225–258}, title = {Multi-Sided Boundary Labeling}, volume = 76, year = 2016 }
Obstructing Visibilities with One Obstacle. Steven Chaplick, Fabian Lipp, Ji-won Park, and Alexander Wolff. In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.), pp. 295–308. Springer-Verlag, 2016.
- [ 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öllenburg, Martin}, keywords = {gd-info1}, pages = {295–308}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Obstructing Visibilities with One Obstacle}, volume = 9801, year = 2016 }
Continuous Generalization of Administrative Boundaries Based on Compatible Triangulations. Dongliang Peng, Alexander Wolff, and Jan-Henrik Haunert. In Proc. 19th AGILE Conference on Geographic Information Science – Geospatial Data in a Changing World, of Lect. Notes Geoinf. Cartogr., T. Sarjakoski, M. Y. Santos, L. T. Sarjakoski (eds.), pp. 399–415. Springer-Verlag, 2016.
- [ 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. Thomas C. van Dijk, Martin Fink, Norbert Fischer, Fabian Lipp, Peter Markfelder, Alexander Ravsky, Subhash Suri, and Alexander Wolff. In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.), pp. 382–398. Springer-Verlag, 2016.

Received best-paper award at GD 2016
- [ 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öllenburg, Martin}, keywords = {gd-info1}, 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 }
Matching Labels and Markers in Historical Maps: An Algorithm with Interactive Postprocessing. Benedikt Budig, Thomas C. van Dijk, and Alexander Wolff. ACM Transactions on Spatial Algorithms and Systems, 2(4), pp. 13:1–24. 2016.
- [ 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 = {sensitivity_analysis}, 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. Michael A. Bekos, Thomas C. van Dijk, Philipp Kindermann, and Alexander Wolff. Journal of Graph Algorithms & Applications, 20(1), pp. 133–158. 2016.
- [ 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 }
Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Fabian Lipp, Alexander Wolff, and Johannes Zink. Algorithms, 9(3), p. article 53, 17 pages. 2016.
- [ 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 }

2015[ to top ]

Pixel and Voxel Representations of Graphs. Md. Jawaherul Alam, Thomas Bläsius, Ignaz Rutter, Torsten Ueckerdt, and Alexander Wolff. In Proc. 23rd Int. Symp. Graph Drawing & Network Vis. (GD’15), Vol. 9411 of Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (eds.), pp. 472–486. Springer-Verlag, 2015.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{abruw-pvrg-GD15, author = {Alam, Md. Jawaherul and Blä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 = {gd-info1}, pages = {472–486}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Pixel and Voxel Representations of Graphs}, volume = 9411, year = 2015 }
Colored Non-Crossing Euclidean Steiner Forest. Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff. In Proc. 26th Annu. Int. Symp. Algorithms Comput. (ISAAC’15), Vol. 9472 of Lecture Notes in Computer Science, K. Elbassioni, K. Makino (eds.), pp. 429–441. Springer-Verlag, 2015.
- [ 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 = {429–441}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Colored Non-Crossing {Euclidean} {Steiner} Forest}, volume = 9472, year = 2015 }
Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Fabian Lipp, ALexander Wolff, and Johannes Zink. In Proc. 23rd Int. Symp. Graph Drawing & Network Vis. (GD’15), Vol. 9411 of Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (eds.), pp. 52–59. Springer-Verlag, 2015.
- [ 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 = {gd-info1}, 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 }
Approximating Minimum Manhattan Networks in Higher Dimensions. Aparna Das, Emden R. Gansner, Michael Kaufmann, Stephen Kobourov, Joachim Spoerhase, and Alexander Wolff. Algorithmica, 71(1), pp. 36–52. 2015.
- [ 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 = {computational_geometry}, number = 1, pages = {36–52}, title = {Approximating Minimum {Manhattan} Networks in Higher Dimensions}, volume = 71, year = 2015 }
Labeling Streets Along a Route in Interactive 3D Maps Using Billboards. Nadine Schwartges, Benjamin Morgan, Jan-Henrik Haunert, and Alexander Wolff. In Proc. 18th AGILE Conf. Geogr. Inform. Sci. (AGILE’15), of Lecture Notes in Geoinformation and Cartography, F. Bacao, M. Y. Santos, M. Painho (eds.), pp. 269–287. Springer-Verlag, 2015.
- [ 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 }
Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends. Michael A. Bekos, Thomas C. van Dijk, Philipp Kindermann, and Alexander Wolff. In Proc. 9th Int. Workshop Algorithms Comput. (WALCOM’15), Vol. 8973 of Lecture Notes in Computer Science, M. S. Rahman, E. Tomita (eds.), pp. 222–233. Springer-Verlag, 2015.
- [ 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 }
Ordering Metro Lines by Block Crossings. Martin Fink, Sergey Pupyrev, and Alexander Wolff. Journal of Graph Algorithms & Applications, 19(1), pp. 111–153. 2015.
- [ 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 }
Solving Optimization Problems on Orthogonal Ray Graphs. Steven Chaplick, Philipp Kindermann, Fabian Lipp, and Alexander Wolff. In Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCGG’15), p. 2 pp. 2015.

Abstract
- [ 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 }

2014[ to top ]

Point Labeling with Sliding Labels in Interactive Maps. Nadine Schwartges, Jan-Henrik Haunert, Alexander Wolff, and Dennis Zwiebler. In Proc. 17th AGILE Conf. Geogr. Inform. Sci. (AGILE’14), of Lecture Notes in Geoinformation and Cartography, J. Huerta, S. Schade, C. Granell (eds.), pp. 295–310. Springer-Verlag, 2014.
- [ 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í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 }
Smooth Orthogonal Drawings of Planar Graphs. Md. Jawaherul Alam, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov, and Alexander Wolff. In Proc. 11th Latin American Sympos. Theor. Inform. (LATIN’14), Vol. 8392 of Lecture Notes in Computer Science, A. Pardo, A. Viola (eds.), pp. 144–155. Springer-Verlag, 2014.
- [ 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 }
Guest Editors’ Foreword (Special Issue of Selected Papers from the 21st Int. Symp. Graph Drawing). Stephen Wismath and Alexander Wolff. Journal of Graph Algorithms & Applications, 18(2), pp. 174–175. 2014.
- [ 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 }
Improved Approximation Algorithms for Box Contact Representations. Michael A. Bekos, Thomas C. van Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff. In Proc. 22nd Annu. Europ. Symp. Algorithms (ESA’14), Vol. 8737 of Lecture Notes in Computer Science, A. Schulz, D. Wagner (eds.), pp. 87–99. Springer-Verlag, 2014.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ 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 }
On Monotone Drawings of Trees. Philipp Kindermann, André Schulz, Joachim Spoerhase, and Alexander Wolff. In Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 488–500. Springer-Verlag, 2014.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{kssw-mdt-GD14, author = {Kindermann, Philipp and Schulz, André and Spoerhase, Joachim and Wolff, Alexander}, booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)}, editor = {Duncan, Christian and Symvonis, Antonios}, keywords = {gd-info1}, pages = {488–500}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {On Monotone Drawings of Trees}, volume = 8871, year = 2014 }
Watch Your Data Structures. Dongliang Peng and Alexander Wolff. In Proc. 22th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK’14), p. 10 pages. Glasgow, 2014.
- [ 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 }
Concentric Metro Maps. Martin Fink, Magnus Lechner, and Alexander Wolff. In Proc. Schematic Mapping Workshop (SMW’14). Wivenhoe Park, 2014.

Poster
- [ 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 }
Labeling Streets in Interactive Maps using Embedded Labels. Nadine Schwartges, Alexander Wolff, and Jan-Henrik Haunert. In Proc. 22nd ACM SIGSPATIAL Int. Conf. Advances Geogr. Inform. Syst. (ACM-GIS’14), Y. Huang, M. Schneider, M. Gertz, J. Krumm, J. Sankaranarayanan (eds.), pp. 517–520. 2014.
- [ 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 }
Semantic Word Cloud Representations: Hardness and Approximation Algorithms. Lukas Barth, Sara Irina Fabrikant, Stephen Kobourov, Anna Lubiw, Martin Nöllenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, Torsten Ueckerdt, and Alexander Wolff. In Proc. 11th Latin American Sympos. Theor. Inform. (LATIN’14), Vol. 8392 of Lecture Notes in Computer Science, A. Pardo, A. Viola (eds.), pp. 514–525. Springer-Verlag, 2014.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{bfklnopsuw-swcrh-LATIN14, author = {Barth, Lukas and Fabrikant, Sara Irina and Kobourov, Stephen and Lubiw, Anna and Nö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 }
Drawing Graphs within Restricted Area. Maximilian Aulbach, Martin Fink, Julian Schuhmann, and Alexander Wolff. In Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 367–379. Springer-Verlag, 2014.
- [ 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 = {gd-info1}, pages = {367–379}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Drawing Graphs within Restricted Area}, volume = 8871, year = 2014 }
Universal Point Sets for Drawing Planar Graphs with Circular Arcs. Patrizio Angelini, David Eppstein, Fabrizio Frati, Michael Kaufmann, Silvain Lazard, Tamara Mchedlidze, Monique Teillaud, and Alexander Wolff. Journal of Graph Algorithms & Applications, 18(3), pp. 313–324. 2014.
- [ 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 = {planar_graphs}, number = 3, pages = {313–324}, title = {Universal Point Sets for Drawing Planar Graphs with Circular Arcs}, volume = 18, year = 2014 }
Luatodonotes: Boundary Labeling for Annotations in Texts. Philipp Kindermann, Fabian Lipp, and Alexander Wolff. In Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 76–88. Springer-Verlag, 2014.
- [ 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 = {gd-info1}, pages = {76–88}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Luatodonotes: Boundary Labeling for Annotations in Texts}, volume = 8871, year = 2014 }

2013[ to top ]

Graph Drawing and Cartography. Alexander Wolff. In Handbook of Graph Drawing and Visualization, R. Tamassia (ed.), pp. 697–736. CRC Press, Boca Raton, FL, 2013.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@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 }
Optimizing Active Ranges for Point Selection in Dynamic Maps. Nadine Schwartges, Dennis Allerkamp, Jan-Henrik Haunert, and Alexander Wolff. In Proc. 16th ICA Generalisation Workshop (ICAGW’13). 2013.

10 pages.
- [ 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 }
Proceedings of the 21st International Symposium on Graph Drawing (GD’13). Stephen Wismath and Alexander Wolff. In Vol. 8242 of Lecture Notes in Computer Science. Springer-Verlag, 2013.
- [ 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 }
Two-Sided Boundary Labeling with Adjacent Sides. Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, and Alexander Wolff. In Proc. 13th Int. Algorithms Data Struct. Symp. (WADS’13), Vol. 8037 of Lecture Notes in Computer Science, F. Dehne, R. Solis-Oba, J.-R. Sack (eds.), pp. 463–474. Springer-Verlag, 2013.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ arxiv ]
@inproceedings{knrssw-2sbla-WADS13, author = {Kindermann, Philipp and Niedermann, Benjamin and Rutter, Ignaz and Schaefer, Marcus and Schulz, André 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 }
Approximating the Generalized Minimum Manhattan Network Problem. Aparna Das, Krzysztof Fleszar, Stephen G. Kobourov, Joachim Spoerhase, Sankar Veeramoni, and Alexander Wolff. In Proc. 24th Annu. Int. Symp. Algorithms Comput. (ISAAC’13), Vol. 8283 of Lecture Notes in Computer Science, L. Cai, S.-W. Cheng, T.-W. Lam (eds.), pp. 722–732. Springer-Verlag, 2013.
- [ 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 }
Universal Point Sets for Planar Graph Drawings with Circular Arcs. Patrizio Angelini, David Eppstein, Michael Kaufmann Fabrizio Frati, Silvain Lazard, Monique Teillaud Tamara Mchedlidze, and Alexander Wolff. In Proc. 25th Canadian Conf. Comput. Geom. (CCCG’13), pp. 117–122. Waterloo, ON, Canada, 2013.
- [ 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 }
Morphing Polylines Based on Least Squares Adjustment. Dongliang Peng, Jan-Henrik Haunert, and Alexander Wolff. In Proc. 16th ICA Generalisation Workshop (ICAGW’13). 2013.

10 pages.
- [ 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 }
Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation. Martin Fink, Jan-Henrik Haunert, Joachim Spoerhase, and Alexander Wolff. IEEE Transactions on Visualization and Computer Graphics, 19(12), pp. 2326–2335. 2013.
- [ 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 }
Drawing Metro Maps using Bézier Curves. Martin Fink, Herman Haverkort, Martin Nöllenburg, Maxwell Roberts, Julian Schuhmann, and Alexander Wolff. In Proc. 20th Int. Sympos. Graph Drawing (GD’12), Vol. 7704 of Lecture Notes in Computer Science, W. Didimo, M. Patrignani (eds.), pp. 463–474. Springer-Verlag, 2013.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{fhnrsw-dmmbc-GD12, author = {Fink, Martin and Haverkort, Herman and Nö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ézier} Curves}, volume = 7704, year = 2013 }
Progress on Partial Edge Drawings. Till Bruckdorfer, Sabine Cornelsen, Carsten Gutwenger, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg, and Alexander Wolff. In Proc. 20th Int. Sympos. Graph Drawing (GD’12), Vol. 7704 of Lecture Notes in Computer Science, W. Didimo, M. Patrignani (eds.), pp. 67–78. Springer-Verlag, 2013.
- [ 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ö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 }

2012[ to top ]

Cover Contact Graphs. Nieves Atienza, Natalia de Castro, Carmen Cortés, M. Ángeles Garrido, Clara I. Grima, Gregorio Hernández, Alberto Márquez, Auxiliadora Moreno-González, Martin Nöllenburg, José Ramon Portillo, Pedro Reyes, Jesús Valenzuela, Maria Trinidad Villar, and Alexander Wolff. Journal of Computational Geometry, 3(1). 2012.
- [ 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és, Carmen and Garrido, M. Ángeles and Grima, Clara I. and Hernández, Gregorio and Márquez, Alberto and Moreno-González, Auxiliadora and Nöllenburg, Martin and Portillo, José Ramon and Reyes, Pedro and Valenzuela, Jesú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. Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, and Alexander Wolff. Algorithmica, 62(1--2), pp. 309–332. 2012.
- [ 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öllenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo I. and Wolff, Alexander}, journal = {Algorithmica}, keywords = {gd-info1}, number = {1–2}, pages = {309–332}, title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability}, volume = 62, year = 2012 }
Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs. Nadine Schwartges, Joachim Spoerhase, and Alexander Wolff. In Proc. 9th Workshop Approx. Online Algorithms (WAOA’11), Vol. 7164 of Lecture Notes in Computer Science, R. Solis-Oba, G. Persiano (eds.), pp. 77–88. Springer-Verlag, 2012.
- [ 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 }
Augmenting the Connectivity of Planar and Geometric Graphs. Ignaz Rutter and Alexander Wolff. Journal of Graph Algorithms & Applications, 16(2), pp. 599–628. 2012.
- [ 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 }
Putting Data on the Map. Stephen Kobourov, Alexander Wolff, and Frank van Ham. In Vol. 2 of Dagstuhl Reports, pp. 51–76. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2012.

Dagstuhl Seminar 12261
- [ 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ür Informatik}, series = {Dagstuhl Reports}, title = {Putting Data on the Map}, volume = 2, year = 2012 }
Algorithms for Labeling Focus Regions. Martin Fink, Jan-Henrik Haunert, André Schulz, Joachim Spoerhase, and Alexander Wolff. IEEE Transactions on Visualization and Computer Graphics, 18(12), pp. 2583–2592. 2012.
- [ 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é and Spoerhase, Joachim and Wolff, Alexander}, journal = {IEEE Transactions on Visualization and Computer Graphics}, keywords = {geographic/geospatial_visualization}, number = 12, pages = {2583–2592}, title = {Algorithms for Labeling Focus Regions}, volume = 18, year = 2012 }
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Martin Fink, Jan-Henrik Haunert, Tamara Mchedlidze, Joachim Spoerhase, and Alexander Wolff. In Proc. Workshop Algorithms Comput. (WALCOM’12), Vol. 7157 of Lecture Notes in Computer Science, M. S. Rahman, S.- ichi Nakano (eds.), pp. 186–197. Springer-Verlag, 2012.
- [ 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 = {gd-info1}, 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 }

2011[ to top ]

Approximating Minimum Manhattan Networks in Higher Dimensions. Aparna Das, Emden R. Gansner, Michael Kaufmann, Stephen Kobourov, Joachim Spoerhase, and Alexander Wolff. In Proc. 19th Annu. Europ. Symp. on Algorithms (ESA’11), Vol. 6942 of Lecture Notes in Computer Science, C. Demetrescu, M. M. Halldórsson (eds.), pp. 49–60. Springer-Verlag, 2011.
- [ 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órsson, Magnú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 }
Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming. Martin Nöllenburg and Alexander Wolff. IEEE Transactions on Visualization and Computer Graphics, 17(5), pp. 626–641. 2011.
- [ 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öllenburg, Martin and Wolff, Alexander}, journal = {IEEE Transactions on Visualization and Computer Graphics}, keywords = {network_visualization}, number = 5, pages = {626–641}, title = {Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming}, volume = 17, year = 2011 }
Schematization in Cartography, Visualization, and Computational Geometry. Jason Dykes, Matthias Müller-Hannemann, and Alexander Wolff. In Vol. 10461 of Dagstuhl Seminar Proceedings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2011.
- [ BibTeX ]
- [ URL ]
@proceedings{dmw-scvcg-11, editor = {Dykes, Jason and Müller-Hannemann, Matthias and Wolff, Alexander}, keywords = {gd-info1}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {Dagstuhl Seminar Proceedings}, title = {Schematization in Cartography, Visualization, and Computational Geometry}, volume = 10461, year = 2011 }

2010[ to top ]

Optimal and Topologically Safe Simplification of Building Footprints. Jan-Henrik Haunert and Alexander Wolff. In Proc. 18th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’10), pp. 192–201. 2010.
- [ 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 }
Computing Large Matchings Fast. Ignaz Rutter and Alexander Wolff. ACM Transactions on Algorithms, 7(1), p. article 1, 21 pages. 2010.
- [ 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 = {maximum_matchings}, number = 1, pages = {article 1, 21 pages}, title = {Computing Large Matchings Fast}, volume = 7, year = 2010 }
Manhattan-Geodesic Embedding of Planar Graphs. Bastian Katz, Marcus Krug, Ignaz Rutter, and Alexander Wolff. In Proc. 17th Int. Sympos. Graph Drawing (GD’09), Vol. 5849 of Lecture Notes in Computer Science, D. Eppstein, E. R. Gansner (eds.), pp. 207–218. Springer-Verlag, 2010.
- [ 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 = {gd-info1}, pages = {207–218}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Manhattan-Geodesic Embedding of Planar Graphs}, volume = 5849, year = 2010 }
Trimming of Graphs, with Application to Point Labeling. Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff. Theory of Computing Systems, 47(3), pp. 613–636. 2010.
- [ 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 = {domino_treewidth}, number = 3, pages = {613–636}, title = {Trimming of Graphs, with Application to Point Labeling}, volume = 47, year = 2010 }
How Alexander the Great Brought the Greeks Together While Inflicting Minimal Damage to the Barbarians. Mark de Berg, Dirk Gerrits, Amirali Khosravi, Ignaz Rutter, Constantinos Tsirogiannis, and Alexander Wolff. In Proc. 26th European Workshop Comput. Geom. (EuroCG’10), pp. 73–76. Dortmund, 2010.
- [ 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 }
Area aggregation in map generalisation by mixed-integer programming. Jan-Henrik Haunert and Alexander Wolff. International Journal of Geographical Information Science, 24(12), pp. 1871–1897. 2010.
- [ 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 = {combinatorial_optimisation}, number = 12, pages = {1871–1897}, title = {Area aggregation in map generalisation by mixed-integer programming}, volume = 24, year = 2010 }
The Traveling Salesman Problem Under Squared Euclidean Distances. Marc de Berg, Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, and Alexander Wolff. In Proc. 27th Int. Sympos. Theoretical Aspects Comput. Sci. (STACS’10), J.-Y. Marion, T. Schwentick (eds.), pp. 239–250. Nancy, 2010.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
@inproceedings{bnsww-tspus-STACS10, address = {Nancy}, author = {de Berg, Marc and van Nijnatten, Fred and Sitters, René 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 }
Optimizing Active Ranges for Consistent Dynamic Map Labeling. Ken Been, Martin Nöllenburg, Sheung-Hung Poon, and Alexander Wolff. Computational Geometry: Theory and Applications, 43(3), pp. 312–328. 2010.
- [ 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öllenburg, Martin and Poon, Sheung-Hung and Wolff, Alexander}, journal = {Computational Geometry: Theory and Applications}, keywords = {dynamic}, number = 3, pages = {312–328}, title = {Optimizing Active Ranges for Consistent Dynamic Map Labeling}, volume = 43, year = 2010 }

2009[ to top ]

Drawing Binary Tanglegrams: An Experimental Evaluation. Martin Nöllenburg, Markus Völker, Alexander Wolff, and Danny Holten. In Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX’09), pp. 106–119. 2009.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{nvwh-dbtee-09, author = {Nöllenburg, Martin and Völker, Markus and Wolff, Alexander and Holten, Danny}, booktitle = {Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX'09)}, keywords = {gd-info1}, pages = {106–119}, title = {Drawing Binary Tanglegrams: An Experimental Evaluation}, year = 2009 }
Untangling a Planar Graph. Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, and Alexander Wolff. Discrete & Computational Geometry, 42(4), pp. 542–569. 2009.
- [ 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íl, Jan and Okamoto, Yoshio and Shin, Chan-Su and Spillner, Andreas and Wolff, Alexander}, journal = {Discrete \& Computational Geometry}, keywords = {gd-info1}, number = 4, pages = {542–569}, title = {Untangling a Planar Graph}, volume = 42, year = 2009 }
A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem. Marc Benkert, Joachim Gudmundsson, Christian Knauer, René van Oostrum, and Alexander Wolff. International Journal of Computational Geometry and Applications, 19(3), pp. 267–288. 2009.
- [ 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é and Wolff, Alexander}, journal = {International Journal of Computational Geometry and Applications}, keywords = {APX-hard}, number = 3, pages = {267–288}, title = {A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem}, volume = 19, year = 2009 }
Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability. Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, and Alexander Wolff. In Proc. 16th Int. Sympos. Graph Drawing (GD’08), Vol. 5417 of Lecture Notes in Computer Science, I. G. Tollis, M. Patrignani (eds.), pp. 324–335. Springer-Verlag, 2009.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
- [ arxiv ]
@inproceedings{bbbnosw-dcbth-09, author = {Buchin, Kevin and Buchin, Maike and Byrka, Jaroslaw and Nöllenburg, 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 }
Matching Points with Rectangles and Squares. Sergey Bereg, Nikolaus Mutsanas, and Alexander Wolff. Computational Geometry: Theory and Applications, 42(2), pp. 93–108. 2009.
- [ 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 = {perfect_matching}, number = 2, pages = {93–108}, title = {Matching Points with Rectangles and Squares}, volume = 42, year = 2009 }
Constructability of Trip-lets. Jeroen Keiren, Freek van Walderveen, and Alexander Wolff. In Proc. 25th European Workshop on Computational Geometry (EuroCG’09), S. Langerman (ed.). 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 }
Constructing Optimal Highways. Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin, and Alexander Wolff. International Journal of Foundations of Computer Science, 20(1), pp. 3–23. 2009.
- [ 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 = {min-max-min_problem}, number = 1, pages = {3–23}, title = {Constructing Optimal Highways}, volume = 20, year = 2009 }

2008[ to top ]

Constructing Interference-Minimal Networks. Marc Benkert, Joachim Gudmundsson, Herman Haverkort, and Alexander Wolff. Computational Geometry: Theory and Applications, 40(3), pp. 179–194. 2008.
- [ 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 = {link_diameter}, number = 3, pages = {179–194}, title = {Constructing Interference-Minimal Networks}, volume = 40, year = 2008 }
Trimming of Graphs, with Application to Point Labeling. Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff. In Proc. 25th Int. Sympos. Theoretical Aspects Comput. Sci. (STACS’08), Vol. 1 of LIPIcs, S. Albers, P. Weil (eds.), pp. 265–276. Bordeaux, 2008.
- [ 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 }
Optimal Simplification of Building Ground Plans. Jan-Henrik Haunert and Alexander Wolff. In Proc. 21st Congress Int. Society Photogrammetry Remote Sensing (ISPRS’08), Technical Commision II/3, Vol. XXXVII, Part B2 of Int. Archives of Photogrammetry, Remote Sensing and Spatial Informat. Sci., pp. 373–378. Beijing, 2008.
- [ 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 }
Optimizing Active Ranges for Consistent Dynamic Map Labeling. Ken Been, Martin Nöllenburg, Sheung-Hung Poon, and Alexander Wolff. In Proc. 24th Annu. ACM Sympos. Comput. Geom. (SoCG’08), pp. 10–19. 2008.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{bnpw-oarcd-08, author = {Been, Ken and Nö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 }
Constructing the City Voronoi Diagram Faster. Robert Görke, Chan-Su Shin, and Alexander Wolff. International Journal of Computational Geometry and Applications, 18(4), pp. 275–294. 2008.
- [ 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örke, Robert and Shin, Chan-Su and Wolff, Alexander}, journal = {International Journal of Computational Geometry and Applications}, keywords = {city_Voronoi_diagram}, number = 4, pages = {275–294}, title = {Constructing the City {Voronoi} Diagram Faster}, volume = 18, year = 2008 }
Morphing Polylines: A Step Towards Continuous Generalization. Martin Nöllenburg, Damian Merrick, Alexander Wolff, and Marc Benkert. Computers, Environment and Urban Systems, 32(4), pp. 248–260. 2008.
- [ 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öllenburg, Martin and Merrick, Damian and Wolff, Alexander and Benkert, Marc}, journal = {Computers, Environment and Urban Systems}, keywords = {dynamic_programming}, number = 4, pages = {248–260}, title = {Morphing Polylines: A Step Towards Continuous Generalization}, volume = 32, year = 2008 }
Augmenting the Connectivity of Planar and Geometric Graphs. Ignaz Rutter and Alexander Wolff. In Proc. Int. Conf. Topological Geom. Graph Theory (TGGT’08), Vol. 31 of Electronic Notes in Discrete Mathematics, pp. 53–56. Paris, 2008.
- [ 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 }
Moving Vertices to Make Drawings Plane. Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, and Alexander Wolff. In Proc. 15th Int. Sympos. Graph Drawing (GD’07), Vol. 4875 of Lecture Notes in Computer Science, S.-H. Hong, T. Nishizeki, W. Quan (eds.), pp. 101–112. Springer-Verlag, 2008.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{gkosw-mvmdp-GD08, author = {Goaoc, Xavier and Kratochví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 }
Delineating Boundaries for Imprecise Regions. Iris Reinbacher, Marc Benkert, Marc van Kreveld, Joseph S.B. Mitchell, Jack Snoeyink, and Alexander Wolff. Algorithmica, 50(3), pp. 386–414. 2008.
- [ 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 }
Decomposing a Simple Polygon into Pseudo-Triangles and Convex Polygons. Stefan Gerdjikov and Alexander Wolff. Computational Geometry: Theory and Applications, 41(1--2), pp. 21–30. 2008.
- [ 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 = {dynamic_programming}, number = {1–2}, pages = {21–30}, title = {Decomposing a Simple Polygon into Pseudo-Triangles and Convex Polygons}, volume = 41, year = 2008 }
Untangling a Planar Graph. Andreas Spillner and Alexander Wolff. In Proc. 34th Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’08), Vol. 4910 of Lecture Notes in Computer Science, V. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková (eds.), pp. 473–484. Springer-Verlag, 2008.
- [ 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äki, Juhani and Bertoni, Alberto and Preneel, Bart and Návrat, Pavol and Bieliková, Mária}, keywords = {myown}, pages = {473–484}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Untangling a Planar Graph}, volume = 4910, year = 2008 }
Computing Large Matchings Fast. Ignaz Rutter and Alexander Wolff. In Proc. 19th ACM-SIAM Sympos. Discrete Algorithms (SODA’08), pp. 183–192. 2008.
- [ 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 }
Cover Contact Graphs. Nieves Atienza, Natalia de Castro, Carmen Cortés, M. Ángeles Garrido, Clara I. Grima, Gregorio Hernández, Alberto Márquez, Auxiliadora Moreno, Martin Nöllenburg, José Ramon Portillo, Pedro Reyes, Jesús Valenzuela, Maria Trinidad Villar, and Alexander Wolff. In Proc. 15th Int. Sympos. Graph Drawing (GD’07), Vol. 4875 of Lecture Notes in Computer Science, S.-H. Hong, T. Nishizeki, W. Quan (eds.), pp. 171–182. Springer-Verlag, 2008.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{accgghmmnprvvw-ccg-08, author = {Atienza, Nieves and de Castro, Natalia and Cortés, Carmen and Garrido, M. Ángeles and Grima, Clara I. and Hernández, Gregorio and Márquez, Alberto and Moreno, Auxiliadora and Nöllenburg, Martin and Portillo, José Ramon and Reyes, Pedro and Valenzuela, Jesú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 = {gd-info1}, pages = {171–182}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Cover Contact Graphs}, volume = 4875, year = 2008 }

2007[ to top ]

Morphing Polygonal Lines: A Step Towards Continuous Generalization. Damian Merrick, Martin Nöllenburg, Alexander Wolff, and Marc Benkert. In Proc. 15th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK’07), pp. 390–399. Maynooth, Ireland, 2007.
- [ BibTeX ]
- [ URL ]
- [ pdf ]
@inproceedings{mnwb-mplst-GISRUK07, address = {Maynooth, Ireland}, author = {Merrick, Damian and Nö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 }
Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps. Marc Benkert, Martin Nöllenburg, Takeaki Uno, and Alexander Wolff. In Proc. 14th Int. Sympos. Graph Drawing (GD’06), Vol. 4372 of Lecture Notes in Computer Science, M. Kaufmann, D. Wagner (eds.), pp. 270–281. Springer-Verlag, 2007.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bnuw-miecw-07, author = {Benkert, Marc and Nöllenburg, Martin and Uno, Takeaki and Wolff, Alexander}, booktitle = {Proc. 14th Int. Sympos. Graph Drawing (GD'06)}, editor = {Kaufmann, Michael and Wagner, Dorothea}, keywords = {gd-info1}, 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 }
Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. Michael A. Bekos, Michael Kaufmann, Antonios Symvonis, and Alexander Wolff. Computational Geometry: Theory and Applications, 36(3), pp. 215–236. 2007.
- [ 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 = {gd-info1}, number = 3, pages = {215–236}, title = {Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps}, volume = 36, year = 2007 }
Geometric Networks and Metric Space Embeddings. Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, and Alexander Wolff. In Vol. 06481 of Dagstuhl Seminar Proceedings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2007.
- [ BibTeX ]
- [ URL ]
- [ pdf ]
@proceedings{gknsw-gnmse-07, editor = {Gudmundsson, Joachim and Klein, Rolf and Narasimhan, Giri and Smid, Michiel and Wolff, Alexander}, keywords = {distortion}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {Dagstuhl Seminar Proceedings}, title = {Geometric Networks and Metric Space Embeddings}, volume = {06481}, year = 2007 }
Configurations with Few Crossings in Topological Graphs. Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. Computational Geometry: Theory and Applications, 37(2), pp. 104–114. 2007.
- [ 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, É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 }
Constructing Optimal Highways. Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin, and Alexander Wolff. In Proc. 13th Conf. Computing: The Australasian Theory Sympos. (CATS’07), Vol. 65 of Conferences in Research and Practice in Information Technology, B. Jay, J. Gudmundsson (eds.), pp. 7–14. Australian Computer Society, 2007.
- [ 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 }
Drawing Subway Maps: A Survey. Alexander Wolff. Informatik – Forschung & Entwicklung, 22(1), pp. 23–44. 2007.
- [ 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 = {gd-info1}, number = 1, pages = {23–44}, title = {Drawing Subway Maps: A Survey}, volume = 22, year = 2007 }
Morphing Polygonal Lines: A Step Towards Continuous Generalization. Damian Merrick, Martin Nöllenburg, Alexander Wolff, and Marc Benkert. In Proc. 23rd European Workshop on Computational Geometry (EWCG’07), O. Aichholzer, T. Hackl (eds.), pp. 6–9. Graz, 2007.
- [ BibTeX ]
- [ pdf ]
@inproceedings{mnwb-mplst-EWCG07, address = {Graz}, author = {Merrick, Damian and Nö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 }
Straightening Drawings of Clustered Hierarchical Graphs. Sergey Bereg, Markus Völker, Alexander Wolff, and Yuanyi Zhang. In Proc. 33rd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’07), Vol. 4362 of Lecture Notes in Computer Science, J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plášil (eds.), pp. 177–186. Springer-Verlag, 2007.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bvwz-sdchg-07, author = {Bereg, Sergey and Vö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 Plášil, František}, keywords = {gd-info1}, pages = {177–186}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Straightening Drawings of Clustered Hierarchical Graphs}, volume = 4362, year = 2007 }

2006[ to top ]

Matching Points with Rectangles and Squares. Sergey Bereg, Nikolaus Mutsanas, and Alexander Wolff. In Proc. 32nd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’06), Vol. 3831 of Lecture Notes in Computer Science, J. Wiedermann, J. Stuller, G. Tel, J. Pokorný, M. Bieliková (eds.), pp. 177–186. Springer-Verlag, 2006.
- [ 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ří and Stuller, Julius and Tel, Gerard and Pokorný, Jaroslav and Bieliková, Má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 }
Pseudo-Convex Decomposition of Simple Polygons. Stefan Gerdjikov and Alexander Wolff. In Proc. 22nd European Workshop on Computational Geometry (EWCG’06), pp. 13–16. Delphi, 2006.
- [ 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 }
Improved Fixed-Parameter Algorithms for Non-Crossing Subgraphs. Magnús M. Halldórsson, Alexander Wolff, and Takeshi Tokuyama. In Proc. ICALP Affiliated Workshop on Improving Exponential-Time Algorithms (iETA’06), pp. 31–38. Venezia, 2006.
- [ BibTeX ]
- [ pdf ]
@inproceedings{htw-ifpan-iETA06, address = {Venezia}, author = {Halldórsson, Magnú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 }
Routing by Landmarks. Urs-Jakob Rüetschi, David Caduff, Sabine Timpf, Frank Schulz, and Alexander Wolff. In Proc. 6th Swiss Transport Research Conf. (STRC’06). Ascona, 2006.

CD-ROM
- [ 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ü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 }
Generalization of Land Cover Maps by Mixed Integer Programming. Jan-Henrik Haunert and Alexander Wolff. In Proc. 14th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’06), pp. 75–82. 2006.
- [ 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 }
A New Approximation Algorithm for Labeling Weighted Points with Sliding Labels. Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff. In Proc. 22nd European Workshop on Computational Geometry (EWCG’06), pp. 137–140. Delphi, 2006.
- [ 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 }
Farthest-Point Queries with Geometric and Combinatorial Constraints. Ovidiu Daescu, Ningfang Mi, Chan-Su Shin, and Alexander Wolff. Computational Geometry: Theory and Applications, 33(3), pp. 174–185. 2006.
- [ 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 = {farthest-point_queries}, number = 3, pages = {174–185}, title = {Farthest-Point Queries with Geometric and Combinatorial Constraints}, volume = 33, year = 2006 }
A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem. Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, René van Oostrum, and Alexander Wolff. In Proc. 12th Annu. Int. Comput. Combinatorics Conf. (COCOON’06), Vol. 4112 of Lecture Notes in Computer Science, D. Z. Chen, D.-T. Lee (eds.), pp. 166–175. Springer-Verlag, 2006.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
@inproceedings{bgkmow-ptaag-06, author = {Benkert, Marc and Gudmundsson, Joachim and Knauer, Christian and Moet, Esther and van Oostrum, René 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 }
The Minimum Manhattan Network Problem: Approximations and Exact Solutions. Marc Benkert, Alexander Wolff, Florian Widmann, and Takeshi Shirabe. Computational Geometry: Theory and Applications, 35(3), pp. 188–208. 2006.
- [ 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 = {approximation_algorithm}, number = 3, pages = {188–208}, title = {The Minimum {Manhattan} Network Problem: Approximations and Exact Solutions}, volume = 35, year = 2006 }
A Mixed-Integer Program for Drawing High-Quality Metro Maps. Martin Nöllenburg and Alexander Wolff. In Proc. 13th Int. Sympos. Graph Drawing (GD’05), Vol. 3843 of Lecture Notes in Computer Science, P. Healy, N. S. Nikolov (eds.), pp. 321–333. Springer-Verlag, 2006.
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
- [ slides ]
@inproceedings{nw-mipdh-06, author = {Nö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 }
A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem. Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, René van Oostrum, and Alexander Wolff. In Proc. 22nd European Workshop on Computational Geometry (EWCG’06), pp. 141–144. Delphi, 2006.
- [ BibTeX ]
- [ pdf ]
@inproceedings{bgkmow-ptaag-06i, address = {Delphi}, author = {Benkert, Marc and Gudmundsson, Joachim and Knauer, Christian and Moet, Esther and van Oostrum, René 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 }
Constructing Interference-Minimal Networks. Marc Benkert, Joachim Gudmundsson, Herman Haverkort, and Alexander Wolff. In Proc. 32nd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’06), Vol. 3831 of Lecture Notes in Computer Science, J. Wiedermann, J. Stuller, G. Tel, J. Pokorný, M. Bieliková (eds.), pp. 166–175. Springer-Verlag, 2006.
- [ 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ří and Stuller, Julius and Tel, Gerard and Pokorný, Jaroslav and Bieliková, Mária}, keywords = {myown}, pages = {166–175}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Constructing Interference-Minimal Networks}, volume = 3831, year = 2006 }

2005[ to top ]

The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation. Marc Benkert, Florian Widmann, and Alexander Wolff. In Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04), Vol. 3742 of Lecture Notes in Computer Science, J. Akiyama, M. Kano, X. Tan (eds.), pp. 16–28. Springer-Verlag, 2005.
- [ 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. Robert Görke and Alexander Wolff. In Proc. 2nd Int. Symp. on Voronoi Diagrams in Science and Engineering (VD’05), pp. 162–172. Seoul, 2005.
- [ BibTeX ]
- [ pdf ]
@inproceedings{gw-ccvdf-VD05, address = {Seoul}, author = {Gö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 }
Delineating Boundaries for Imprecise Regions. Iris Reinbacher, Marc Benkert, Marc van Kreveld, and Alexander Wolff. In Proc. 21st European Workshop on Computational Geometry (EWCG’05), pp. 127–130. Eindhoven, 2005.
- [ 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 }
Spanning Trees with Few Crossings in Geometric and Topological Graphs. Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. In Proc. 21st European Workshop on Computational Geometry (EWCG’05), pp. 195–198. Eindhoven, 2005.
- [ BibTeX ]
- [ pdf ]
@inproceedings{kssw-stfcg-05, address = {Eindhoven}, author = {Knauer, Christian and Schramm, É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 }
Optimal Spanners for Axis-Aligned Rectangles. Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, and Alexander Wolff. Computational Geometry: Theory and Applications, 30(1), pp. 59–77. 2005.
- [ 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 = {isothetic_rectangles}, number = 1, pages = {59–77}, title = {Optimal Spanners for Axis-Aligned Rectangles}, volume = 30, year = 2005 }
Configurations with Few Crossings in Topological Graphs. Christian Knauer, Étienne Schramm, Andreas Spillner, and Alexander Wolff. In Proc. 16th Annu. Int. Symp. Algorithms Comput. (ISAAC’05), Vol. 3827 of Lecture Notes in Computer Science, X. Deng, D.-Z. Du (eds.), pp. 604–613. Springer-Verlag, 2005.
- [ 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, É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 }
Delineating Boundaries for Imprecise Regions. Iris Reinbacher, Marc Benkert, Marc van Kreveld, Joseph S.B. Mitchell, and Alexander Wolff. In Proc. 13th Annu. Europ. Symp. on Algorithms (ESA’05), Vol. 3669 of Lecture Notes in Computer Science, G. S. Brodal, S. Leonardi (eds.), pp. 143–154. Springer-Verlag, 2005.
- [ 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. Ovidiu Daescu, Ningfang Mi, Chan-Su Shin, and Alexander Wolff. In Proc. 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04), Vol. 3742 of Lecture Notes in Computer Science, J. Akiyama, M. Kano, X. Tan (eds.), pp. 62–75. Springer-Verlag, 2005.
- [ 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 }
Geometrische Netzwerke und ihre Visualisierung. Alexander Wolff. 2005, June.
- [ BibTeX ]
- [ pdf ]
@misc{w-gniv-05, author = {Wolff, Alexander}, howpublished = {Habilitationsschrift (kumulativ), Fakultät für Informatik, Universität Karlsruhe}, keywords = {gd-info1}, month = {06}, school = {Fakultät für Informatik, Universität Karlsruhe}, title = {{Geometrische Netzwerke und ihre Visualisierung}}, year = 2005 }
Constructing Interference-Minimal Networks. Marc Benkert, Joachim Gudmundsson, Herman Haverkort, and Alexander Wolff. In Proc. 21st European Workshop on Computational Geometry (EWCG’05), pp. 203–206. Eindhoven, 2005.
- [ 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 }
Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. Michael A. Bekos, Michael Kaufmann, Antonios Symvonis, and Alexander Wolff. In Proc. 12th Int. Sympos. Graph Drawing (GD’04), Vol. 3383 of Lecture Notes in Computer Science, J. Pach (ed.), pp. 49–59. Springer-Verlag, 2005.
- [ 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á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 }
Constructing the City Voronoi Diagram Faster. Robert Görke and Alexander Wolff. In Proc. 21st European Workshop on Computational Geometry (EWCG’05), pp. 155–158. Eindhoven, 2005.
- [ BibTeX ]
- [ pdf ]
@inproceedings{gw-ccvdf-EWCG05, address = {Eindhoven}, author = {Gö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 }

2004[ to top ]

Optimal Spanners for Axis-Aligned Rectangles. Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, and Alexander Wolff. In Proc. 20th European Workshop on Computational Geometry (EWCG’04), pp. 97–100. Sevilla, 2004.
- [ 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 }
Algorithms for the Placement of Diagrams on Maps. Marc van Kreveld, Étienne Schramm, and Alexander Wolff. In Proc. 12th Int. ACM Symp. Advances Geogr. Inform. Syst. (ACM-GIS’04), D. Pfoder, I. F. Cruz, M. Ronthaler (eds.), pp. 222–231. 2004.
- [ 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, É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 = {cartographic_visualization}, pages = {222–231}, title = {Algorithms for the Placement of Diagrams on Maps}, year = 2004 }
The Minimum Manhattan Network Problem: Approximations and Exact Solutions. Alexander Wolff, Marc Benkert, and Takeshi Shirabe. In Proc. 20th European Workshop on Computational Geometry (EWCG’04), pp. 209–212. Sevilla, 2004.
- [ 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 }
Facility Location and the Geometric Minimum-Diameter Spanning Tree. Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, Chan-Su Shin, and Alexander Wolff. Computational Geometry: Theory and Applications, 27(1), pp. 87–106. 2004.
- [ 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 = {approximation_algorithm}, number = 1, pages = {87–106}, title = {Facility Location and the Geometric Minimum-Diameter Spanning Tree}, volume = 27, year = 2004 }
Farthest-Point Queries with Geometric and Combinatorial Constraints. Ovidiu Daescu, Ningfang Mi, Chan-Su Shin, and Alexander Wolff. In Proc. 20th European Workshop on Computational Geometry (EWCG’04), pp. 45–48. Sevilla, 2004.
- [ 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 }
Farthest-Point Queries with Geometric and Combinatorial Constraints. Ovidiu Daescu, Ningfang Mi, Chan-Su Shin, and Alexander Wolff. In Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04), pp. 110–111. Tokyo, 2004.
- [ 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. Marc Benkert, Florian Widmann, and Alexander Wolff. In Abstracts 8th Japanese Conf. on Discrete and Computational Geometry (JCDCG’04), pp. 85–86. Tokyo, 2004.
- [ 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 }
Web-Based Delineation of Imprecise Regions. Avi Arampatzis, Marc van Kreveld, Iris Reinbacher, Christopher B. Jones, Subodh Vaid, Paul Clough, Hideo Joho, Mark Sanderson, Marc Benkert, and Alexander Wolff. In Proc. Workshop on Geographic Information Retrieval at SIGIR’04. Sheffield, 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 }

2003[ to top ]

Labeling Points with Weights. Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, Takeaki Uno, and Alexander Wolff. Algorithmica, 38(2), pp. 341–362. 2003.
- [ 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 = {label_placement}, number = 2, pages = {341–362}, title = {Labeling Points with Weights}, volume = 38, year = 2003 }

2002[ to top ]

A Tutorial for Designing Flexible Geometric Algorithms. Vikas Kapoor, Dietmar Kühl, and Alexander Wolff. Algorithmica, 33(1), pp. 52–70. 2002.
- [ 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ü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 }
Facility Location and the Geometric Minimum-Diameter Spanning Tree. Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, Chan-Su Shin, and Alexander Wolff. In Proc. 5th Int. Workshop Approx. Algorithms Combin. Optim. (APPROX’02), Vol. 2462 of Lecture Notes in Computer Science, K. Jansen, S. Leonardi, V. Vazirani (eds.), pp. 146–160. Springer-Verlag, 2002.
- [ 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 }
Towards an Evaluation of Quality for Names Placement Methods. Steven van Dijk, Marc van Kreveld, Tycho Strijk, and Alexander Wolff. International Journal of Geographical Information Science, 16(7), pp. 641–661. 2002.
- [ 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 = {classification}, number = 7, pages = {641–661}, title = {Towards an Evaluation of Quality for Names Placement Methods}, volume = 16, year = 2002 }
Approximating the Geometric Minimum-Diameter Spanning Tree. Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, Chan-Su Shin, and Alexander Wolff. In Proc. 18th European Workshop on Computational Geometry (EWCG’02), pp. 41–45. War-szawa, 2002.
- [ 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 }
A Simple Factor-2/3 Approximation Algorithm for Two-Circle Point Labeling. Alexander Wolff, Michael Thon, and Yinfeng Xu. International Journal of Computational Geometry and Applications, 12(4), pp. 269–281. 2002.
- [ 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 = {multi-label_point_labeling}, number = 4, pages = {269–281}, title = {A Simple Factor-2/3 Approximation Algorithm for Two-Circle Point Labeling}, volume = 12, year = 2002 }

2001[ to top ]

Labeling Points with Circles. Tycho Strijk and Alexander Wolff. International Journal of Computational Geometry and Applications, 11(2), pp. 181–195. 2001.
- [ 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 = {packing_problem}, number = 2, pages = {181–195}, title = {Labeling Points with Circles}, volume = 11, year = 2001 }
Etiquetado de puntos alineados. Mari Ángeles Garrido, Alberto Márquez, Claudia Iturriaga, José Ramon Portillo, Pedro Reyes, and Alexander Wolff. In Proc. IX Encuentros de Geometría Computacional (EGC’01), pp. 285–294. Girona, 2001.
- [ BibTeX ]
@inproceedings{gmiprw-epa-EGC01, address = {Girona}, author = {Garrido, Mari Ángeles and Márquez, Alberto and Iturriaga, Claudia and Portillo, José Ramon and Reyes, Pedro and Wolff, Alexander}, booktitle = {Proc. IX Encuentros de Geometría Computacional (EGC'01)}, keywords = {myown}, pages = {285–294}, title = {Etiquetado de puntos alineados}, year = 2001 }
Labeling Points with Weights. Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, and Alexander Wolff. In Proc. 12th Annu. Int. Symp. Algorithms Comput. (ISAAC’01), Vol. 2223 of Lecture Notes in Computer Science, P. Eades, T. Takaoka (eds.), pp. 610–622. Springer-Verlag, 2001.
- [ 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 }
Labeling Subway Lines. Mari Ángeles Garrido, Claudia Iturriaga, Alberto Márquez, José Ramon Portillo, Pedro Reyes, and Alexander Wolff. In Proc. 12th Annu. Int. Symp. Algorithms Comput. (ISAAC’01), Vol. 2223 of Lecture Notes in Computer Science, P. Eades, T. Takaoka (eds.), pp. 649–659. Springer-Verlag, 2001.
- [ 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 Ángeles and Iturriaga, Claudia and Márquez, Alberto and Portillo, José 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 }
Three Rules Suffice for Good Label Placement. Frank Wagner, Alexander Wolff, Vikas Kapoor, and Tycho Strijk. Algorithmica, 30(2), pp. 334–349. 2001.
- [ 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 = {experimental_comparison}, number = 2, pages = {334–349}, title = {Three Rules Suffice for Good Label Placement}, volume = 30, year = 2001 }
Labeling Points with Weights. Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, and Alexander Wolff. In Proc. 17th European Workshop on Computational Geometry (EWCG’01), pp. 97–100. Berlin, 2001.
- [ 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 }

2000[ to top ]

A Better Lower Bound for Two-Circle Point Labeling. Alexander Wolff, Michael Thon, and Yinfeng Xu. In Proc. 11th Annu. Int. Symp. Algorithms Comput. (ISAAC’00), Vol. 1969 of Lecture Notes in Computer Science, D. Lee, S.-H. Teng (eds.), pp. 422–431. Springer-Verlag, 2000.
- [ 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 }
New Algorithms for Two-Label Point Labeling. Zhongping Qin, Alexander Wolff, Yinfeng Xu, and Binhai Zhu. In Proc. 8th Annu. Europ. Symp. on Algorithms (ESA’00), Vol. 1879 of Lecture Notes in Computer Science, M. Paterson (ed.), pp. 368–379. Springer-Verlag, 2000.
- [ 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 Simple and Efficient Algorithm for High-Quality Line Labeling. Alexander Wolff, Lars Knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal. In Innovations in GIS VII: GeoComputation, P. M. Atkinson, D. J. Martin (eds.), pp. 147–159. Taylor & Francis, 2000.
- [ 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 }

1999[ to top ]

A Combinatorial Framework for Map Labeling. Frank Wagner and Alexander Wolff. In Proc. 6th Int. Sympos. Graph Drawing (GD’98), Vol. 1547 of Lecture Notes in Computer Science, S. H. Whitesides (ed.), pp. 316–331. Springer-Verlag, 1999.
- [ 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 }
Towards an Evaluation of Quality for Label Placement Methods. Steven van Dijk, Marc van Kreveld, Tycho Strijk, and Alexander Wolff. In Proc. 19th Int. Cartographic Conf. (ICA’99), pp. 905–913. Int. Cartographic Association, Ottawa, 1999.
- [ 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 Simple and Efficient Algorithm for High-Quality Line Labeling. Pankaj K. Agarwal, Lars Knipping, Marc van Kreveld, Tycho Strijk, and Alexander Wolff. In Proc. 15th European Workshop on Computational Geometry (EWCG’99), pp. 93–96. Sophia-Antipolis, 1999.
- [ 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 }
Point Labeling with Sliding Labels. Marc van Kreveld, Tycho Strijk, and Alexander Wolff. Computational Geometry: Theory and Applications, 13(1), pp. 21–47. 1999.
- [ 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 = {map_labeling}, number = 1, pages = {21–47}, title = {Point Labeling with Sliding Labels}, volume = 13, year = 1999 }
A Simple and Efficient Algorithm for High-Quality Line Labeling. Alexander Wolff, Lars Knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal. In Proc. 7th Annu. Geograph. Inform. Sci. Research Conf. UK (GISRUK’99), D. Martin, F. Wu (eds.), pp. 146–150. Southampton, 1999.
- [ 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 }
Automated Label Placement in Theory and Practice. Technical Report (PhD dissertation), . Alexander Wolff. PhD dissertation. Fachbereich Mathematik und Informatik, Freie Universität Berlin, 1999, May.
- [ BibTeX ]
- [ pdf ]
@phdthesis{w-alptp-99, author = {Wolff, Alexander}, keywords = {myown}, month = {05}, school = {Fachbereich Mathematik und Informatik, Freie Universit{\"a}t Berlin}, title = {Automated Label Placement in Theory and Practice}, type = {PhD thesis}, year = 1999 }

1998[ to top ]

The Hardness of Approximating Set Cover. Alexander Wolff. In Lectures on Proof Verification and Approximation Algorithms, Vol. 1367, E. W. Mayr, H. J. Prömel, A. Steger (eds.), pp. 249–262. Springer-Verlag, 1998.
- [ 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ömel, {Hans Jü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 }
MakeIt! -- Generating and Maintaining Makefiles Automatically. Sven Schönherr and Alexander Wolff. In Proc. Workshop on Algorithms and Experiments (ALEX’98), R. Battini, A. A. Bertossi (eds.), pp. 165–174. Trento, 1998.
- [ 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ö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 }
Point Set Labeling with Sliding Labels. Marc van Kreveld, Tycho Strijk, and Alexander Wolff. In Proc. 14th Annu. ACM Sympos. Comput. Geom. (SoCG’98), pp. 337–346. 1998.
- [ 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 }

1997[ to top ]

A Practical Map Labeling Algorithm. Frank Wagner and Alexander Wolff. Computational Geometry: Theory and Applications, 7(5--6), pp. 387–404. 1997.
- [ 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 = {computational_cartography}, number = {5–6}, pages = {387–404}, title = {A Practical Map Labeling Algorithm}, volume = 7, year = 1997 }

1996[ to top ]

The Map-Labeling Bibliography. Alexander Wolff and Tycho Strijk. 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 }

1995[ to top ]

Map Labeling. Technical Report (Master thesis), . Alexander Wolff. Master thesis. Fachbereich Mathematik und Informatik, Freie Universität Berlin, 1995, May.
- [ BibTeX ]
@mastersthesis{w-ml-95, author = {Wolff, Alexander}, keywords = {myown}, month = {05}, school = {Fachbereich Mathematik und Informatik, Freie Universit{\"a}t Berlin}, title = {Map Labeling}, year = 1995 }
Fast and Reliable Map Labeling. Frank Wagner and Alexander Wolff. In Proc. 9th Int. Symp. Computer Science for Environment Protection (CSEP’95), H. K. und Werner Pillmann (ed.), pp. 667–675. Metropolis, 1995.
- [ 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 }
Map Labeling Heuristics: Provably Good and Practically Useful. Frank Wagner and Alexander Wolff. In Proc. 11th Annu. ACM Sympos. Comput. Geom. (SoCG’95), pp. 109–118. 1995.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
@inproceedings{ww-mlhpg-95, author = {Wagner, Frank and Wolff, Alexander}, booktitle = {Proc. 11th Annu. ACM Sympos. Comput. Geom. (SoCG'95)}, keywords = {experimental_comparison}, pages = {109–118}, title = {Map Labeling Heuristics: Provably Good and Practically Useful}, year = 1995 }
An Efficient and Effective Approximation Algorithm for the Map Labeling Problem. Frank Wagner and Alexander Wolff. In Proc. 3rd Annu. Europ. Symp. on Algorithms (ESA’95), Vol. 979 of Lecture Notes in Computer Science, P. Spirakis (ed.), pp. 420–433. Springer-Verlag, 1995.
- [ 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 }

To top

Publications (chronologically)

Data privacy protection

Data privacy protection