Document

**Published in:** LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Level Planarity (CLP), each level y is equipped with a partial order ≺_y on its vertices and in the desired drawing the left-to-right order of vertices on level y has to be a linear extension of ≺_y. Ordered Level Planarity (OLP) corresponds to the special case of CLP where the given partial orders ≺_y are total orders. Previous results by Brückner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans. Alg. 2019] state that both CLP and OLP are NP-hard even in severely restricted cases. In particular, they remain NP-hard even when restricted to instances whose width (the maximum number of vertices that may share a common level) is at most two. In this paper, we focus on the other dimension: we study the parameterized complexity of CLP and OLP with respect to the height (the number of levels).
We show that OLP parameterized by the height is complete with respect to the complexity class XNLP, which was first studied by Elberfeld, Stockhusen, and Tantau [Algorithmica 2015] (under a different name) and recently made more prominent by Bodlaender, Groenland, Nederlof, and Swennenhuis [FOCS 2021]. It contains all parameterized problems that can be solved nondeterministically in time f(k)⋅ n^O(1) and space f(k)⋅ log n (where f is a computable function, n is the input size, and k is the parameter). If a problem is XNLP-complete, it lies in XP, but is W[t]-hard for every t.
In contrast to the fact that OLP parameterized by the height lies in XP, it turns out that CLP is NP-hard even when restricted to instances of height 4. We complement this result by showing that CLP can be solved in polynomial time for instances of height at most 3.

Václav Blažej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. Constrained and Ordered Level Planarity Parameterized by the Number of Levels. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.SoCG.2024.20, author = {Bla\v{z}ej, V\'{a}clav and Klemz, Boris and Klesen, Felix and Sieper, Marie Diana and Wolff, Alexander and Zink, Johannes}, title = {{Constrained and Ordered Level Planarity Parameterized by the Number of Levels}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {20:1--20:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.20}, URN = {urn:nbn:de:0030-drops-199652}, doi = {10.4230/LIPIcs.SoCG.2024.20}, annote = {Keywords: Parameterized Complexity, Graph Drawing, XNLP, XP, W\lbrackt\rbrack-hard, Level Planarity, Planar Poset Diagram, Computational Geometry} }

Document

**Published in:** LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest number of vertices or edges such that the remaining graph can be drawn without crossings. We study both problems in a book-embedding setting for ordered graphs, that is, graphs with a fixed vertex order. In this setting, the vertices lie on a straight line, called the spine, in the given order, and each edge must be drawn on one of several pages of a book such that every edge has at most a fixed number of crossings. In book embeddings, there is another way to reduce or avoid crossings; namely by using more pages. The minimum number of pages needed to draw an ordered graph without any crossings is its (fixed-vertex-order) page number.
We show that the page number of an ordered graph with n vertices and m edges can be computed in 2^m ⋅ n^𝒪(1) time. An 𝒪(log n)-approximation of this number can be computed efficiently. We can decide in 2^𝒪(d √k log (d+k)) ⋅ n^𝒪(1) time whether it suffices to delete k edges of an ordered graph to obtain a d-planar layout (where every edge crosses at most d other edges) on one page. As an additional parameter, we consider the size h of a hitting set, that is, a set of points on the spine such that every edge, seen as an open interval, contains at least one of the points. For h = 1, we can efficiently compute the minimum number of edges whose deletion yields fixed-vertex-order page number p. For h > 1, we give an XP algorithm with respect to h+p. Finally, we consider spine+t-track drawings, where some but not all vertices lie on the spine. The vertex order on the spine is given; we must map every vertex that does not lie on the spine to one of t tracks, each of which is a straight line on a separate page, parallel to the spine. In this setting, we can minimize in 2ⁿ ⋅ n^𝒪(1) time either the number of crossings or, if we disallow crossings, the number of tracks.

Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating Crossings in Ordered Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.SWAT.2024.1, author = {Agrawal, Akanksha and Cabello, Sergio and Kaufmann, Michael and Saurabh, Saket and Sharma, Roohani and Uno, Yushi and Wolff, Alexander}, title = {{Eliminating Crossings in Ordered Graphs}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {1:1--1:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.1}, URN = {urn:nbn:de:0030-drops-200417}, doi = {10.4230/LIPIcs.SWAT.2024.1}, annote = {Keywords: Ordered graphs, book embedding, edge deletion, d-planar, hitting set} }

Document

**Published in:** LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

A mixed interval graph is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph G, an interval u receives a lower (different) color than an interval v if G contains arc (u,v) (edge {u,v}). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020].
For coloring general mixed interval graphs, we present a min {ω(G), λ(G)+1}-approximation algorithm, where ω(G) is the size of a largest clique and λ(G) is the length of a longest directed path in G. For the subclass of bidirectional interval graphs (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs.
We introduce a new natural class of mixed interval graphs, which we call containment interval graphs. In such a graph, there is an arc (u,v) if interval u contains interval v, and there is an edge {u,v} if u and v overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. Coloring and Recognizing Mixed Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gutowski_et_al:LIPIcs.ISAAC.2023.36, author = {Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Klesen, Felix and Rz\k{a}\.{z}ewski, Pawe{\l} and Wolff, Alexander and Zink, Johannes}, title = {{Coloring and Recognizing Mixed Interval Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {36:1--36:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.36}, URN = {urn:nbn:de:0030-drops-193388}, doi = {10.4230/LIPIcs.ISAAC.2023.36}, annote = {Keywords: Interval Graphs, Mixed Graphs, Graph Coloring} }

Document

**Published in:** LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

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.
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)²) [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 Ω(n²) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances.
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.

Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff. Bounding and Computing Obstacle Numbers of Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.ESA.2022.11, author = {Balko, Martin and Chaplick, Steven and Ganian, Robert and Gupta, Siddharth and Hoffmann, Michael and Valtr, Pavel and Wolff, Alexander}, title = {{Bounding and Computing Obstacle Numbers of Graphs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.11}, URN = {urn:nbn:de:0030-drops-169495}, doi = {10.4230/LIPIcs.ESA.2022.11}, annote = {Keywords: Obstacle representation, Obstacle number, Visibility, NP-hardness, FPT} }

Document

**Published in:** LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. 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.
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 Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.

Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander}, title = {{Adjacency Graphs of Polyhedral Surfaces}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.11}, URN = {urn:nbn:de:0030-drops-138107}, doi = {10.4230/LIPIcs.SoCG.2021.11}, annote = {Keywords: polyhedral complexes, realizability, contact representation} }

Document

**Published in:** LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n-10 edges.
We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n-12 edges and that there are n-vertex arc-RAC graphs with 4.5n - O(√n) edges.

Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. Drawing Graphs with Circular Arcs and Right-Angle Crossings. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.SWAT.2020.21, author = {Chaplick, Steven and F\"{o}rster, Henry and Kryven, Myroslav and Wolff, Alexander}, title = {{Drawing Graphs with Circular Arcs and Right-Angle Crossings}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.21}, URN = {urn:nbn:de:0030-drops-122687}, doi = {10.4230/LIPIcs.SWAT.2020.21}, annote = {Keywords: circular arcs, right-angle crossings, edge density, charging argument} }

Document

**Published in:** Dagstuhl Reports, Volume 9, Issue 5 (2019)

This report documents the program and the outcomes of Dagstuhl Seminar 19192 "Visual Analytics for Sets over Time and Space", which brought together 29 researchers working on visualization (i) from a theoretical point of view (graph drawing, computational geometry, and cognition), (ii) from a temporal point of view (visual analytics and information visualization over time, HCI), and (iii) from a space-time point of view (cartography, GIScience).
The goal of the seminar was to identify specific theoretical and practical problems that need to be solved in order to create dynamic and interactive set visualizations that take into account time and space, and to begin working on these problems.
The first 1.5 days were reserved for overview presentations from representatives of the different communities, for presenting open problems, and for forming interdisciplinary working groups that will focus on some of the identified open problems as a group. There were three survey talks, ten short talks, and one panel with three contributors.
The remaining three days consisted of open mic sessions, working-group meetings, and progress reports.
Five working groups were formed that investigated several of the open research questions.
Abstracts of the talks and a report from each working group are included in this report.

Sara Irina Fabrikant, Silvia Miksch, and Alexander Wolff. Visual Analytics for Sets over Time and Space (Dagstuhl Seminar 19192). In Dagstuhl Reports, Volume 9, Issue 5, pp. 31-56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{fabrikant_et_al:DagRep.9.5.31, author = {Fabrikant, Sara Irina and Miksch, Silvia and Wolff, Alexander}, title = {{Visual Analytics for Sets over Time and Space (Dagstuhl Seminar 19192)}}, pages = {31--56}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {5}, editor = {Fabrikant, Sara Irina and Miksch, Silvia and Wolff, Alexander}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.5.31}, URN = {urn:nbn:de:0030-drops-113806}, doi = {10.4230/DagRep.9.5.31}, annote = {Keywords: Geovisualization, graph drawing, information visualization, set visualization, visual analytics} }

Document

**Published in:** LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network design. To the best of our knowledge, only special cases of this problem have been considered so far.
Stabbing is a weighted geometric set cover problem, which we show to be NP-hard. While for general set cover the best possible approximation ratio is Theta(log n), it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODA'12] generalize earlier results by Varadarajan [STOC'10] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity.
Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.

Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff. Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ISAAC.2018.61, author = {Chan, Timothy M. and van Dijk, Thomas C. and Fleszar, Krzysztof and Spoerhase, Joachim and Wolff, Alexander}, title = {{Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {61:1--61:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.61}, URN = {urn:nbn:de:0030-drops-100094}, doi = {10.4230/LIPIcs.ISAAC.2018.61}, annote = {Keywords: Geometric optimization, NP-hard, approximation, shallow-cell complexity, line stabbing} }

Document

**Published in:** LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

In the classical Steiner tree problem, one is given an undirected, connected graph G=(V,E) with non-negative edge costs and a set of terminals T subseteq V. The objective is to find a minimum-cost edge set E' subseteq E that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of rho = ln(4)+epsilon < 1.39. In this paper, we study a natural generalization, the multi-level Steiner tree (MLST) problem: given a nested sequence of terminals T_1 subset ... subset T_k subseteq V, compute nested edge sets E_1 subseteq ... subseteq E_k subseteq E that span the corresponding terminal sets with minimum total cost.
The MLST problem and variants thereof have been studied under names such as Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two natural heuristics with approximation factor O(k). Based on these, we introduce a composite algorithm that requires 2^k Steiner tree computations. We determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio and needs at most 2k Steiner tree computations. We compare five algorithms experimentally on several classes of graphs using four types of graph generators. We also implemented an integer linear program for MLST to provide ground truth. Our combined algorithm outperforms the others both in theory and in practice when the number of levels is small (k <= 22), which works well for applications such as designing multi-level infrastructure or network visualization.

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. Multi-Level Steiner Trees. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:LIPIcs.SEA.2018.15, author = {Ahmed, Reyan and Angelini, Patrizio and Sahneh, Faryad Darabi 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}, title = {{Multi-Level Steiner Trees}}, booktitle = {17th International Symposium on Experimental Algorithms (SEA 2018)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-070-5}, ISSN = {1868-8969}, year = {2018}, volume = {103}, editor = {D'Angelo, Gianlorenzo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.15}, URN = {urn:nbn:de:0030-drops-89506}, doi = {10.4230/LIPIcs.SEA.2018.15}, annote = {Keywords: Approximation algorithm, Steiner tree, multi-level graph representation} }

Document

**Published in:** Dagstuhl Reports, Volume 2, Issue 6 (2012)

This report documents the program and the outcomes of Dagstuhl Seminar 12261 ``Putting Data on the Map''.

Stephen Kobourov, Alexander Wolff, and Frank van Ham. Putting Data on the Map (Dagstuhl Seminar 12261). In Dagstuhl Reports, Volume 2, Issue 6, pp. 51-76, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{kobourov_et_al:DagRep.2.6.51, author = {Kobourov, Stephen and Wolff, Alexander and van Ham, Frank}, title = {{Putting Data on the Map (Dagstuhl Seminar 12261)}}, pages = {51--76}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {2}, number = {6}, editor = {Kobourov, Stephen and Wolff, Alexander and van Ham, Frank}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.6.51}, URN = {urn:nbn:de:0030-drops-37303}, doi = {10.4230/DagRep.2.6.51}, annote = {Keywords: Information Visualization, Cartography, GIScience, Computational Geometry, Graph Drawing, Cognition} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10461, Schematization in Cartography, Visualization, and Computational Geometry (2011)

The Dagstuhl Seminar 10461 ``Schematization in Cartography,
Visualization, and Computational Geometry'' was held November
14--19, 2010 in Schloss Dagstuhl~-- Leibniz Center for Informatics.
The seminar brought together experts from the areas graph drawing,
information visualization, geographic information science,
computational geometry, very-large-scale integrated circuit (VLSI)
layout, and underground mining. The aim was to discuss problems
that arise when computing the layout of complex networks under
angular restrictions (that govern the way in which the network edges
are drawn).
This collection consists of abstracts of three different types of
contributions that reflect the different stages of the seminar;
(a)~survey talks about the role of schematization in the various
communities represented at the seminar, (b)~talks in the open
problem and open mic sessions, and (c)~introductory talks.

Jason Dykes, Matthias Müller-Hannemann, and Alexander Wolff. 10461 Abstracts Collection and Summary – Schematization in Cartography, Visualization, and Computational Geometry. In Schematization in Cartography, Visualization, and Computational Geometry. Dagstuhl Seminar Proceedings, Volume 10461, pp. 1-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{dykes_et_al:DagSemProc.10461.1, author = {Dykes, Jason and M\"{u}ller-Hannemann, Matthias and Wolff, Alexander}, title = {{10461 Abstracts Collection and Summary – Schematization in Cartography, Visualization, and Computational Geometry}}, booktitle = {Schematization in Cartography, Visualization, and Computational Geometry}, pages = {1--36}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10461}, editor = {Jason Dykes and Mattias M\"{u}ller-Hannemann and Alexander Wolff}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10461.1}, URN = {urn:nbn:de:0030-drops-30859}, doi = {10.4230/DagSemProc.10461.1}, annote = {Keywords: Information visualization, geo-visualization, geographic information systems, cartography, graph drawing, VLSI layout, underground mining, cartographic generalization, schematization, building simplification, orthogonal graph drawing, octilinear layout, schematic maps, Steiner trees} }

Document

**Published in:** LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Let $P$ be a set of points in $\Reals^d$, and let $\alpha \ge 1$ be a real number. We define the distance between two points $p,q\in P$ as $|pq|^{\alpha}$, where $|pq|$ denotes the standard Euclidean distance between $p$ and $q$. We denote the traveling salesman problem under this distance function by \tsp($d,\alpha$). We design a 5-approximation algorithm for \tsp(2,2) and generalize this result to obtain an approximation factor of $3^{\alpha-1}+\sqrt{6}^{\,\alpha}\!/3$ for $d=2$ and all $\alpha\ge2$.
We also study the variant Rev-\tsp\ of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-\tsp$(2,\alpha)$ with $\alpha\ge2$, and we show that Rev-\tsp$(d, \alpha)$ is \apx-hard if
$d\ge3$ and $\alpha>1$. The \apx-hardness proof carries over to \tsp$(d, \alpha)$ for the same parameter ranges.

Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff, and Mark de Berg. The Traveling Salesman Problem under Squared Euclidean Distances. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 239-250, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{vannijnatten_et_al:LIPIcs.STACS.2010.2458, author = {van Nijnatten, Fred and Sitters, Ren\'{e} and Woeginger, Gerhard J. and Wolff, Alexander and de Berg, Mark}, title = {{The Traveling Salesman Problem under Squared Euclidean Distances}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {239--250}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2458}, URN = {urn:nbn:de:0030-drops-24580}, doi = {10.4230/LIPIcs.STACS.2010.2458}, annote = {Keywords: Geometric traveling salesman problem, power-assignment in wireless networks, distance-power gradient, NP-hard, APX-hard} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

For $t,g>0$, a vertex-weighted graph of total weight $W$ is
$(t,g)$-trimmable if it contains a vertex-induced subgraph of total
weight at least $(1-1/t)W$ and with no simple path of more than $g$
edges. A family of graphs is trimmable if for each constant $t>0$,
there is a constant $g=g(t)$ 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. Based on this
result, we derive a polynomial-time approximation scheme for the
problem of labeling weighted points with nonoverlapping sliding
labels of unit height and given lengths so as to maximize the total
weight of the labeled points. This settles one of the last major
open questions in the theory of map labeling.

Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff. Trimming of Graphs, with Application to Point Labeling. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 265-276, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.STACS.2008.1350, author = {Erlebach, Thomas and Hagerup, Torben and Jansen, Klaus and Minzlaff, Moritz and Wolff, Alexander}, title = {{Trimming of Graphs, with Application to Point Labeling}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {265--276}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1350}, URN = {urn:nbn:de:0030-drops-13509}, doi = {10.4230/LIPIcs.STACS.2008.1350}, annote = {Keywords: Trimming weighted graphs, domino treewidth, planar graphs, point-feature label placement, map labeling, polynomial-time approximation schemes} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007)

The Dagstuhl Seminar 06481 ``Geometric Networks and Metric Space
Embeddings'' was held from November~26 to December~1, 2006 in the
International Conference and Research Center (IBFI), Schloss
Dagstuhl. During the seminar, several participants presented their
current research, and ongoing work and open problems were discussed.
In this paper we describe the seminar topics, we have compiled a
list of open questions that were posed during the seminar, there is
a list of all talks and there are abstracts of the presentations
given during the seminar. Links to extended abstracts or full
papers are provided where available.

Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, and Alexander Wolff. 06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings. In Geometric Networks and Metric Space Embeddings. Dagstuhl Seminar Proceedings, Volume 6481, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:DagSemProc.06481.1, author = {Gudmundsson, Joachim and Klein, Rolf and Narasimhan, Giri and Smid, Michiel and Wolff, Alexander}, title = {{06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings}}, booktitle = {Geometric Networks and Metric Space Embeddings}, pages = {1--21}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {6481}, editor = {Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.1}, URN = {urn:nbn:de:0030-drops-10291}, doi = {10.4230/DagSemProc.06481.1}, annote = {Keywords: Geometric networks, metric space embeddings, phylogenetic networks, spanners, dilation, distortion} }