Search Results

Documents authored by Klute, Fabian

Document
DOI: 10.4230/LIPIcs.GD.2024.35
On k-Plane Insertion into Plane Drawings

Authors: Julia Katheder, Philipp Kindermann, Fabian Klute, Irene Parada, and Ignaz Rutter

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

Abstract
We introduce the k-Plane Insertion into Plane drawing (k-PIP) problem: given a plane drawing of a planar graph G and a set F of edges, insert the edges in F into the drawing such that the resulting drawing is k-plane. In this paper, we show that the problem is NP-complete for every k ≥ 1, even when G is biconnected and the set F of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that k = 1 and G is a triangulation.
Cite as

Julia Katheder, Philipp Kindermann, Fabian Klute, Irene Parada, and Ignaz Rutter. On k-Plane Insertion into Plane Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 35:1-35:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{katheder_et_al:LIPIcs.GD.2024.35,
  author =	{Katheder, Julia and Kindermann, Philipp and Klute, Fabian and Parada, Irene and Rutter, Ignaz},
  title =	{{On k-Plane Insertion into Plane Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{35:1--35:11},
  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.35},
  URN =		{urn:nbn:de:0030-drops-213190},
  doi =		{10.4230/LIPIcs.GD.2024.35},
  annote =	{Keywords: Graph drawing, edge insertion, k-planarity}
}
Document
Graph Drawing Contest Report
DOI: 10.4230/LIPIcs.GD.2024.41
Graph Drawing Contest Report (Graph Drawing Contest Report)

Authors: Sara Di Bartolomeo, Fabian Klute, Debajyoti Mondal, and Jules Wulms

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

Abstract
This report describes the 31st Annual Graph Drawing Contest, held in conjunction with the 32nd International Symposium on Graph Drawing and Network Visualization (GD'24) at TU Wien, Vienna, Austria. The mission of the Graph Drawing Contest is to monitor and challenge the current state of the art in graph-drawing technology. This year’s edition featured two categories, a creative track in which participants visualized a dataset based on the Olympic medal track-record of countries and a live challenge held at the conference where participants had to draw a graph on a given point-set with as few crossings as possible.
Cite as

Sara Di Bartolomeo, Fabian Klute, Debajyoti Mondal, and Jules Wulms. Graph Drawing Contest Report (Graph Drawing Contest Report). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dibartolomeo_et_al:LIPIcs.GD.2024.41,
  author =	{Di Bartolomeo, Sara and Klute, Fabian and Mondal, Debajyoti and Wulms, Jules},
  title =	{{Graph Drawing Contest Report}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{41:1--41:13},
  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.41},
  URN =		{urn:nbn:de:0030-drops-213256},
  doi =		{10.4230/LIPIcs.GD.2024.41},
  annote =	{Keywords: Information Visualization, Graph Drawing Contest}
}
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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.72
Crossing-Optimal Extension of Simple Drawings

Authors: Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, the extension problem of simple drawings has only recently been shown to be NP-hard even for inserting a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing.
Cite as

Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber. Crossing-Optimal Extension of Simple Drawings. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 72:1-72:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.ICALP.2021.72,
  author =	{Ganian, Robert and Hamm, Thekla and Klute, Fabian and Parada, Irene and Vogtenhuber, Birgit},
  title =	{{Crossing-Optimal Extension of Simple Drawings}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{72:1--72:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.72},
  URN =		{urn:nbn:de:0030-drops-141412},
  doi =		{10.4230/LIPIcs.ICALP.2021.72},
  annote =	{Keywords: Simple drawings, Extension problems, Crossing minimization, FPT-algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.31
Extending Nearly Complete 1-Planar Drawings in Polynomial Time

Authors: Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G and a drawing H of H, the extension problem asks whether H can be extended into a drawing of G while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when H can be obtained from G by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision algorithm.
Cite as

Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg. Extending Nearly Complete 1-Planar Drawings in Polynomial Time. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.MFCS.2020.31,
  author =	{Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Klute, Fabian and N\"{o}llenburg, Martin},
  title =	{{Extending Nearly Complete 1-Planar Drawings in Polynomial Time}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.31},
  URN =		{urn:nbn:de:0030-drops-126998},
  doi =		{10.4230/LIPIcs.MFCS.2020.31},
  annote =	{Keywords: Extension problems, 1-planarity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.43
Extending Partial 1-Planar Drawings

Authors: Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing. In such an extension problem, we are given a tuple (G,H,ℋ) consisting of a graph G, a connected subgraph H of G and a drawing ℋ of H, and the task is to extend ℋ into a drawing of G while maintaining some desired property of the drawing, such as planarity. In this paper we study the problem of extending partial 1-planar drawings, which are drawings in the plane that allow each edge to have at most one crossing. In addition we consider the subclass of IC-planar drawings, which are 1-planar drawings with independent crossings. Recognizing 1-planar graphs as well as IC-planar graphs is NP-complete and the NP-completeness easily carries over to the extension problem. Therefore, our focus lies on establishing the tractability of such extension problems in a weaker sense than polynomial-time tractability. Here, we show that both problems are fixed-parameter tractable when parameterized by the number of edges missing from H, i.e., the edge deletion distance between H and G. The second part of the paper then turns to a more powerful parameterization which is based on measuring the vertex+edge deletion distance between the partial and complete drawing, i.e., the minimum number of vertices and edges that need to be deleted to obtain H from G.
Cite as

Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg. Extending Partial 1-Planar Drawings. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ICALP.2020.43,
  author =	{Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Klute, Fabian and N\"{o}llenburg, Martin},
  title =	{{Extending Partial 1-Planar Drawings}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.43},
  URN =		{urn:nbn:de:0030-drops-124509},
  doi =		{10.4230/LIPIcs.ICALP.2020.43},
  annote =	{Keywords: Extension problems, 1-planarity, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.53
Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts

Authors: Fabian Klute and Martin Nöllenburg

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k >= 1, extending the previously studied case k=0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k=1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k=1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm.
Cite as

Fabian Klute and Martin Nöllenburg. Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{klute_et_al:LIPIcs.SoCG.2018.53,
  author =	{Klute, Fabian and N\"{o}llenburg, Martin},
  title =	{{Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.53},
  URN =		{urn:nbn:de:0030-drops-87663},
  doi =		{10.4230/LIPIcs.SoCG.2018.53},
  annote =	{Keywords: Graph Drawing, Circular Layouts, Crossing Minimization, Circle Graphs, Bounded-Degree Maximum-Weight Induced Subgraphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.33
On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem

Authors: Robert Ganian, Fabian Klute, and Sebastian Ordyniak

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve the main open question stated in Betzler, Bredereck, Niedermeier and Uhlmann (2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.
Cite as

Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2018.33,
  author =	{Ganian, Robert and Klute, Fabian and Ordyniak, Sebastian},
  title =	{{On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.33},
  URN =		{urn:nbn:de:0030-drops-85140},
  doi =		{10.4230/LIPIcs.STACS.2018.33},
  annote =	{Keywords: bounded-degree vertex deletion, feedback vertex set, parameterized algorithms, treecut width}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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