11 Search Results for "Terziadis, Soeren"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.16
Designing Compact ILPs via Fast Witness Verification

Authors: Michał Włodarczyk

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preprocessing for problems without polynomial kernels, still aiming at producing instances that are easily solvable in practice. Specifically, we ask for which parameterized problems an instance (I,k) can be reduced in polynomial time to an integer linear program (ILP) with poly(k) constraints. We show that this property coincides with the parameterized complexity class WK[1], previously studied in the context of Turing kernelization lower bounds. In turn, the class WK[1] enjoys an elegant characterization in terms of witness verification protocols: a yes-instance should admit a witness of size poly(k) that can be verified in time poly(k). By combining known data structures with new ideas, we design such protocols for several problems, such as r-Way Cut, Vertex Multiway Cut, Steiner Tree, and Minimum Common String Partition, thus showing that they can be modeled by compact ILPs. We also present explicit ILP and MILP formulations for Weighted Vertex Cover on graphs with small (unweighted) vertex cover number. We believe that these results will provide a background for a systematic study of ILP-oriented preprocessing procedures for parameterized problems.
Cite as

Michał Włodarczyk. Designing Compact ILPs via Fast Witness Verification. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.IPEC.2025.16,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Designing Compact ILPs via Fast Witness Verification}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.16},
  URN =		{urn:nbn:de:0030-drops-251481},
  doi =		{10.4230/LIPIcs.IPEC.2025.16},
  annote =	{Keywords: integer programming, kernelization, nondeterminism, multiway cut}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.32
The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Authors: Mario Grobler and Sebastian Siebertz

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Mario Grobler and Sebastian Siebertz. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.IPEC.2025.32,
  author =	{Grobler, Mario and Siebertz, Sebastian},
  title =	{{The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.32},
  URN =		{urn:nbn:de:0030-drops-251644},
  doi =		{10.4230/LIPIcs.IPEC.2025.32},
  annote =	{Keywords: PACE 2025 Report, Dominating Set, Hitting Set, Algorithm Engineering, FPT, Heuristics}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.17
Visualizing Treewidth

Authors: Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.
Cite as

Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg. Visualizing Treewidth. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.GD.2025.17,
  author =	{Chiu, Alvin and Depian, Thomas and Eppstein, David and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Visualizing Treewidth}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.17},
  URN =		{urn:nbn:de:0030-drops-250034},
  doi =		{10.4230/LIPIcs.GD.2025.17},
  annote =	{Keywords: Graph drawing, witness drawings, pathwidth, treewidth}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.44
Recovering Graphs from Their Witness Unit Square Representation (Poster Abstract)

Authors: Maarten Löffler, Frank Staals, and Soeren Terziadis

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A wUSR of a graph G is a set of unit squares in the plane, one per vertex, if two vertices have an edge in G if their squares overlap and the overlap contains no witness. We present an output sensitive algorithm to compute a graph G based on its given witness unit square representation.
Cite as

Maarten Löffler, Frank Staals, and Soeren Terziadis. Recovering Graphs from Their Witness Unit Square Representation (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 44:1-44:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.GD.2025.44,
  author =	{L\"{o}ffler, Maarten and Staals, Frank and Terziadis, Soeren},
  title =	{{Recovering Graphs from Their Witness Unit Square Representation}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{44:1--44:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.44},
  URN =		{urn:nbn:de:0030-drops-250306},
  doi =		{10.4230/LIPIcs.GD.2025.44},
  annote =	{Keywords: proximity graphs, geometric intersection graphs, witness representation, unit square intersection graph, output sensitive algorithm, range searching}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.36
Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

Authors: Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).
Cite as

Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf. Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brunck_et_al:LIPIcs.GD.2025.36,
  author =	{Brunck, Florestan and Chang, Hsien-Chih and L\"{o}ffler, Maarten and Ophelders, Tim and Schlipf, Lena},
  title =	{{Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.36},
  URN =		{urn:nbn:de:0030-drops-250220},
  doi =		{10.4230/LIPIcs.GD.2025.36},
  annote =	{Keywords: Curve Arrangements, Reconfiguration, Curve Arrangements, NP-hardness, Fixed-Parameter Tractability, Puzzle Generation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.21
A Unified FPT Framework for Crossing Number Problems

Authors: Éric Colin de Verdière and Petr Hliněný

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to ℤ_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.
Cite as

Éric Colin de Verdière and Petr Hliněný. A Unified FPT Framework for Crossing Number Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2025.21,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Hlin\v{e}n\'{y}, Petr},
  title =	{{A Unified FPT Framework for Crossing Number Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.21},
  URN =		{urn:nbn:de:0030-drops-244897},
  doi =		{10.4230/LIPIcs.ESA.2025.21},
  annote =	{Keywords: computational geometry, fixed-parameter tractability, graph drawing, graph embedding, crossing number, two-dimensional simplicial complex, surface}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.26
The PACE 2024 Parameterized Algorithms and Computational Experiments Challenge: One-Sided Crossing Minimization

Authors: Philipp Kindermann, Fabian Klute, and Soeren Terziadis

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
This article is a report by the challenge organizers on the 9th Parameterized Algorithms and Computational Experiments Challenge (PACE 2024). As was common in previous iterations of the competition, this year’s iteration implemented an exact and heuristic track for a parameterized problem that has gained attention in the theory community. This year’s challenge is about the One-Sided Crossing Minimization Problem (OSCM). In the exact track, the competition participants were asked to develop an exact algorithm that can solve as many instances as possible from a benchmark set of 100 instances – with a time limit of 30 minutes per instance. In the heuristic track, the task must be accomplished within 5 minutes, however, the result in this track is not required to be optimal. New this year is the parameterized track, which has the same rules as the exact track, but instances are guaranteed to have small cutwidth. As in previous iterations, the organizers handed out awards to the best solutions in all tracks and to the best student submissions.
Cite as

Philipp Kindermann, Fabian Klute, and Soeren Terziadis. The PACE 2024 Parameterized Algorithms and Computational Experiments Challenge: One-Sided Crossing Minimization. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kindermann_et_al:LIPIcs.IPEC.2024.26,
  author =	{Kindermann, Philipp and Klute, Fabian and Terziadis, Soeren},
  title =	{{The PACE 2024 Parameterized Algorithms and Computational Experiments Challenge: One-Sided Crossing Minimization}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.26},
  URN =		{urn:nbn:de:0030-drops-222521},
  doi =		{10.4230/LIPIcs.IPEC.2024.26},
  annote =	{Keywords: One-Sided Crossing Minimization, Algorithm Engineering, FPT, Heuristics}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.32
PACE Solver Description: Martin_J_Geiger

Authors: Martin Josef Geiger

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
This extended abstract outlines our contribution to the Parameterized Algorithms and Computational Experiments Challenge (PACE), which invited to work on the one-sided crossing minimization problem. Our ideas are primarily based on the principles of Iterated Local Search and Variable Neighborhood Search. For obvious reasons, the initial alternative stems from the barycenter heuristic. This first sequence (permutation) of nodes is then quickly altered/ improved by a set of operators, keeping the elite configuration while allowing for worsening moves and hence, escaping local optima.
Cite as

Martin Josef Geiger. PACE Solver Description: Martin_J_Geiger. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 32:1-32:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{geiger:LIPIcs.IPEC.2024.32,
  author =	{Geiger, Martin Josef},
  title =	{{PACE Solver Description: Martin\underlineJ\underlineGeiger}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{32:1--32:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.32},
  URN =		{urn:nbn:de:0030-drops-222587},
  doi =		{10.4230/LIPIcs.IPEC.2024.32},
  annote =	{Keywords: PACE 2024, one-sided crossing minimization, Variable Neighborhood Search, Iterated Local Search}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.26
Constrained Boundary Labeling

Authors: Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Finally, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions.
Cite as

Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger. Constrained Boundary Labeling. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ISAAC.2024.26,
  author =	{Depian, Thomas and N\"{o}llenburg, Martin and Terziadis, Soeren and Wallinger, Markus},
  title =	{{Constrained Boundary Labeling}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.26},
  URN =		{urn:nbn:de:0030-drops-221539},
  doi =		{10.4230/LIPIcs.ISAAC.2024.26},
  annote =	{Keywords: Boundary labeling, Grouping constraints, Ordering constraints}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.22
Boundary Labeling in a Circular Orbit

Authors: Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Boundary labeling is a well-known method for displaying short textual labels for a set of point features in a figure alongside the boundary of that figure. Labels and their corresponding points are connected via crossing-free leaders. We propose orbital boundary labeling as a new variant of the problem, in which (i) the figure is enclosed by a circular contour and (ii) the labels are placed as disjoint circular arcs in an annulus-shaped orbit around the contour. The algorithmic objective is to compute an orbital boundary labeling with the minimum total leader length. We identify several parameters that define the corresponding problem space: two leader types (straight or orbital-radial), label size and order, presence of candidate label positions, and constraints on where a leader attaches to its label. Our results provide polynomial-time algorithms for many variants and NP-hardness for others, using a variety of geometric and combinatorial insights.
Cite as

Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, and Jules Wulms. Boundary Labeling in a Circular Orbit. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonerath_et_al:LIPIcs.GD.2024.22,
  author =	{Bonerath, Annika and N\"{o}llenburg, Martin and Terziadis, Soeren and Wallinger, Markus and Wulms, Jules},
  title =	{{Boundary Labeling in a Circular Orbit}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.22},
  URN =		{urn:nbn:de:0030-drops-213060},
  doi =		{10.4230/LIPIcs.GD.2024.22},
  annote =	{Keywords: External labeling, Orthoradial drawing, NP-hardness, Polynomial algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.34
Minimum Link Fencing

Authors: Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.
Cite as

Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu. Minimum Link Fencing. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2022.34,
  author =	{Bhore, Sujoy and Klute, Fabian and L\"{o}ffler, Maarten and N\"{o}llenburg, Martin and Terziadis, Soeren and Villedieu, Ana\"{i}s},
  title =	{{Minimum Link Fencing}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.34},
  URN =		{urn:nbn:de:0030-drops-173191},
  doi =		{10.4230/LIPIcs.ISAAC.2022.34},
  annote =	{Keywords: computational geometry, polygon nesting, polygon separation}
}
  • Refine by Type
  • 11 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 6 2025
  • 4 2024
  • 1 2022

  • Refine by Author
  • 5 Terziadis, Soeren
  • 4 Nöllenburg, Martin
  • 3 Löffler, Maarten
  • 2 Depian, Thomas
  • 2 Klute, Fabian
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Computational geometry
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Mathematics of computing → Graph theory
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Fixed parameter tractability
  • Show More...

  • Refine by Keyword
  • 2 Algorithm Engineering
  • 2 FPT
  • 2 Heuristics
  • 2 NP-hardness
  • 2 computational geometry
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact