Search Results

Documents authored by Rutter, Ignaz

Document
DOI: 10.4230/LIPIcs.GD.2024.10
Constrained Outer-String Representations

Authors: Therese Biedl, Sabine Cornelsen, Jan Kratochvíl, and Ignaz Rutter

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

Abstract
An outer-string representation of a graph is an intersection representation in which each vertex is represented by a curve that is contained in the unit disk and has at least one endpoint on the boundary of the unit disk. In an outer-1-string representation the curves representing any two vertices are in addition allowed to intersect at most once. In this paper, we consider the following constrained version: Given a graph G plus a cyclic order v_1,…,v_n of the vertices in G, test whether G has an outer-string or an outer-1-string representation in which the curves representing v_1,…,v_n intersect the boundary of the unit disk in this order. We first show that a graph has an outer-string representation for all possible cyclic orders of the vertices if and only if the graph is the complement of a chordal graph. Then we turn towards the situation where one particular cyclic order of the vertices is fixed. We characterize the chordal graphs admitting a constrained outer-string representation and the trees and cycles admitting a constrained outer-1-string representation. The characterizations yield polynomial-time recognition and construction algorithms; in the case of outer-1-string representations the run time is linear. We also show how to decide in polynomial time whether an arbitrary graph admits a constrained L-shaped outer-1-string representation. In an L-shaped representation the curves are 1-bend orthogonal polylines anchored on a horizontal line, and they are contained in the half-plane below that line. However, not even all paths with a constrained outer-1-string representation admit one with L-shapes. We show that 2-bend orthogonal polylines are sufficient for trees and cycles with a constrained outer-1-string representation.
Cite as

Therese Biedl, Sabine Cornelsen, Jan Kratochvíl, and Ignaz Rutter. Constrained Outer-String Representations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.GD.2024.10,
  author =	{Biedl, Therese and Cornelsen, Sabine and Kratochv{\'\i}l, Jan and Rutter, Ignaz},
  title =	{{Constrained Outer-String Representations}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{10:1--10:18},
  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.10},
  URN =		{urn:nbn:de:0030-drops-212942},
  doi =		{10.4230/LIPIcs.GD.2024.10},
  annote =	{Keywords: String representation, outer-string, outer-1-string, chordal graphs, trees, polynomial-time algorithms, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.13
The Price of Upwardness

Authors: Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff

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

Abstract
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k ≥ 1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-k-planarity testing is NP-complete already for k = 1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.
Cite as

Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff. The Price of Upwardness. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.GD.2024.13,
  author =	{Angelini, Patrizio and Biedl, Therese and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Hong, Seok-Hee and Liotta, Giuseppe and Patrignani, Maurizio and Pupyrev, Sergey and Rutter, Ignaz and Wolff, Alexander},
  title =	{{The Price of Upwardness}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{13:1--13:20},
  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.13},
  URN =		{urn:nbn:de:0030-drops-212977},
  doi =		{10.4230/LIPIcs.GD.2024.13},
  annote =	{Keywords: upward drawings, beyond planarity, upward k-planarity, upward outer-1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.19
Weakly Leveled Planarity with Bounded Span

Authors: Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, and Ioannis G. Tollis

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

Abstract
This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly y-monotone curve. A graph is s-span weakly leveled planar if it admits such a drawing where the edges have span at most s; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Θ(log n)-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, and Ioannis G. Tollis. Weakly Leveled Planarity with Bounded Span. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2024.19,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Frati, Fabrizio and Gupta, Siddharth and Kindermann, Philipp and Liotta, Giuseppe and Rutter, Ignaz and Tollis, Ioannis G.},
  title =	{{Weakly Leveled Planarity with Bounded Span}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{19:1--19:19},
  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.19},
  URN =		{urn:nbn:de:0030-drops-213035},
  doi =		{10.4230/LIPIcs.GD.2024.19},
  annote =	{Keywords: Leveled planar graphs, edge span, graph drawing, edge-length ratio}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.25
Parameterized Algorithms for Beyond-Planar Crossing Numbers

Authors: Miriam Münch and Ignaz Rutter

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

Abstract
Beyond-planar graph classes are usually defined via forbidden configurations or patterns in a drawing. In this paper, we formalize these concepts on a combinatorial level and show that, for any fixed family ℱ of crossing patterns, deciding whether a given graph G admits a drawing that avoids all patterns in F and that has at most c crossings is FPT w.r.t. c. In particular, we show that for any fixed k, deciding whether a graph is k-planar, k-quasi-planar, fan-crossing, fan-crossing-free or min-k-planar, respectively, is FPT with respect to the corresponding beyond-planar crossing number.
Cite as

Miriam Münch and Ignaz Rutter. Parameterized Algorithms for Beyond-Planar Crossing Numbers. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{munch_et_al:LIPIcs.GD.2024.25,
  author =	{M\"{u}nch, Miriam and Rutter, Ignaz},
  title =	{{Parameterized Algorithms for Beyond-Planar Crossing Numbers}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{25:1--25:16},
  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.25},
  URN =		{urn:nbn:de:0030-drops-213096},
  doi =		{10.4230/LIPIcs.GD.2024.25},
  annote =	{Keywords: FPT, Beyond-planarity, Crossing-number, Crossing Patterns}
}
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
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.50
Level Planarity Is More Difficult Than We Thought (Poster Abstract)

Authors: Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter, and Peter Stumpf

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

Abstract
We consider three simple quadratic-time algorithms for Level Planarity and give a level-planar instance that they either falsely classify as negative or for which they output a non-planar drawing.
Cite as

Simon D. Fink, Matthias Pfretzschner, Ignaz Rutter, and Peter Stumpf. Level Planarity Is More Difficult Than We Thought (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 50:1-50:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.GD.2024.50,
  author =	{Fink, Simon D. and Pfretzschner, Matthias and Rutter, Ignaz and Stumpf, Peter},
  title =	{{Level Planarity Is More Difficult Than We Thought}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{50:1--50:3},
  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.50},
  URN =		{urn:nbn:de:0030-drops-213341},
  doi =		{10.4230/LIPIcs.GD.2024.50},
  annote =	{Keywords: level planarity, 2-SAT, simple algorithm, counterexample}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.51
Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation (Poster Abstract)

Authors: Jakob Baumann, Ignaz Rutter, and Dirk Sudholt

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

Abstract
Evolutionary algorithms (EAs) are universal solvers inspired by principles of natural evolution. In many applications, EAs produce astonishingly good solutions. To complement recent theoretical advances in the analysis of EAs on graph drawing [Baumann et al., 2024], we contribute a fundamental empirical study. We consider the so-called One-Sided Bipartite Crossing Minimisation (OBCM): given two layers of a bipartite graph and a fixed horizontal order of vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We empirically analyse the performance of simple EAs for OBCM and compare different mutation operators on the underlying permutation ordering problem: exchanging two elements (exchange), swapping adjacent elements (swap) and jumping an element to a new position (jump). EAs using jumps easily outperform all deterministic algorithms in terms of solution quality after a reasonable number of generations. We also design variations of the best-performing EAs to reduce the execution time for each generation. The improved EAs can obtain the same solution quality as before and run up to 100 times faster.
Cite as

Jakob Baumann, Ignaz Rutter, and Dirk Sudholt. Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:LIPIcs.GD.2024.51,
  author =	{Baumann, Jakob and Rutter, Ignaz and Sudholt, Dirk},
  title =	{{Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{51:1--51:3},
  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.51},
  URN =		{urn:nbn:de:0030-drops-213353},
  doi =		{10.4230/LIPIcs.GD.2024.51},
  annote =	{Keywords: Mutation Operator, Layered Graphs, Crossing Minimisation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.90
Simultaneous Representation of Interval Graphs in the Sunflower Case

Authors: Ignaz Rutter and Peter Stumpf

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
A simultaneous representation of (vertex-labeled) graphs G_1,… ,G_k consists of a (geometric) intersection representation R_i for each graph G_i such that each vertex v is represented by the same geometric object in each R_i for which G_i contains v. While Jampani and Lubiw showed that the existence of simultaneous interval representations for k = 2 can be tested efficiently (2010), testing it for graphs where k is part of the input is NP-complete (Bok and Jedličková, 2018). An important special case of simultaneous representations is the sunflower case, where G_i ∩ G_j = (V(G_i)∩ V(G_j),E(G_i)∩ E(G_j)) is the same graph for each i ≠ j. We give an O(∑_{i=1}^k (|V(G_i)|+|E(G_i)|))-time algorithm for deciding the existence of a simultaneous interval representation for the sunflower case, even when k is part of the input. This answers an open question of Jampani and Lubiw.
Cite as

Ignaz Rutter and Peter Stumpf. Simultaneous Representation of Interval Graphs in the Sunflower Case. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 90:1-90:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rutter_et_al:LIPIcs.ESA.2023.90,
  author =	{Rutter, Ignaz and Stumpf, Peter},
  title =	{{Simultaneous Representation of Interval Graphs in the Sunflower Case}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{90:1--90:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.90},
  URN =		{urn:nbn:de:0030-drops-187435},
  doi =		{10.4230/LIPIcs.ESA.2023.90},
  annote =	{Keywords: Interval Graphs, Sunflower Case, Simultaneous Representation, Recognition, Geometric Intersection Graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.51
Partial and Simultaneous Transitive Orientations via Modular Decompositions

Authors: Miriam Münch, Ignaz Rutter, and Peter Stumpf

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

Abstract
A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.
Cite as

Miriam Münch, Ignaz Rutter, and Peter Stumpf. Partial and Simultaneous Transitive Orientations via Modular Decompositions. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{munch_et_al:LIPIcs.ISAAC.2022.51,
  author =	{M\"{u}nch, Miriam and Rutter, Ignaz and Stumpf, Peter},
  title =	{{Partial and Simultaneous Transitive Orientations via Modular Decompositions}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{51:1--51:16},
  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.51},
  URN =		{urn:nbn:de:0030-drops-173369},
  doi =		{10.4230/LIPIcs.ISAAC.2022.51},
  annote =	{Keywords: representation extension, simultaneous representation, comparability graph, permutation graph, circular permutation graph, modular decomposition}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.25
Extending Partial Representations of Circle Graphs in Near-Linear Time

Authors: Guido Brückner, Ignaz Rutter, and Peter Stumpf

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph H ⊆ G and a representation H of H. The question is whether G admits a representation G whose restriction to H is H. We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in O((n + m) α(n + m)) time, where α is the inverse Ackermann function. This improves over an O(n³)-time algorithm by Chaplick, Fulek and Klavík [2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.
Cite as

Guido Brückner, Ignaz Rutter, and Peter Stumpf. Extending Partial Representations of Circle Graphs in Near-Linear Time. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bruckner_et_al:LIPIcs.MFCS.2022.25,
  author =	{Br\"{u}ckner, Guido and Rutter, Ignaz and Stumpf, Peter},
  title =	{{Extending Partial Representations of Circle Graphs in Near-Linear Time}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.25},
  URN =		{urn:nbn:de:0030-drops-168233},
  doi =		{10.4230/LIPIcs.MFCS.2022.25},
  annote =	{Keywords: circle graphs, partial representation extension, split decomposition tree, recognition algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.19
Untangling Circular Drawings: Algorithms and Complexity

Authors: Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We consider the problem of untangling a given (non-planar) straight-line circular drawing δ_G of an outerplanar graph G = (V,E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift°(δ_G) as the minimum number of vertices that need to be shifted to resolve all crossings of δ_G. We show that the problem Circular Untangling, asking whether shift°(δ_G) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift°(δ_G) ≤ ⌊n/2⌋-1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings.
Cite as

Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu. Untangling Circular Drawings: Algorithms and Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2021.19,
  author =	{Bhore, Sujoy and Li, Guangping and N\"{o}llenburg, Martin and Rutter, Ignaz and Wu, Hsiang-Yun},
  title =	{{Untangling Circular Drawings: Algorithms and Complexity}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154528},
  doi =		{10.4230/LIPIcs.ISAAC.2021.19},
  annote =	{Keywords: graph drawing, straight-line drawing, outerplanarity, NP-hardness, untangling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.19
Synchronized Planarity with Applications to Constrained Planarity Problems

Authors: Thomas Bläsius, Simon D. Fink, and Ignaz Rutter

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. Synchronized Planarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that Synchronized Planarity can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of Synchronized Planarity. In particular, this lets us solve Clustered Planarity in quadratic time, where the most efficient previously known algorithm has an upper bound of O(n⁸).
Cite as

Thomas Bläsius, Simon D. Fink, and Ignaz Rutter. Synchronized Planarity with Applications to Constrained Planarity Problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2021.19,
  author =	{Bl\"{a}sius, Thomas and Fink, Simon D. and Rutter, Ignaz},
  title =	{{Synchronized Planarity with Applications to Constrained Planarity Problems}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.19},
  URN =		{urn:nbn:de:0030-drops-146009},
  doi =		{10.4230/LIPIcs.ESA.2021.19},
  annote =	{Keywords: Planarity Testing, Constrained Planarity, Cluster Planarity, Atomic Embeddability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.43
Experimental Comparison of PC-Trees and PQ-Trees

Authors: Simon D. Fink, Matthias Pfretzschner, and Ignaz Rutter

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
PQ-trees and PC-trees are data structures that represent sets of linear and circular orders, respectively, subject to constraints that specific subsets of elements have to be consecutive. While equivalent to each other, PC-trees are conceptually much simpler than PQ-trees; updating a PC-tree so that a set of elements becomes consecutive requires only a single operation, whereas PQ-trees use an update procedure that is described in terms of nine transformation templates that have to be recursively matched and applied. Despite these theoretical advantages, to date no practical PC-tree implementation is available. This might be due to the original description by Hsu and McConnell [Hsu et al., 2003] in some places only sketching the details of the implementation. In this paper, we describe two alternative implementations of PC-trees. For the first one, we follow the approach by Hsu and McConnell, filling in the necessary details and also proposing improvements on the original algorithm. For the second one, we use a different technique for efficiently representing the tree using a Union-Find data structure. In an extensive experimental evaluation we compare our implementations to a variety of other implementations of PQ-trees that are available on the web as part of academic and other software libraries. Our results show that both PC-tree implementations beat their closest fully correct competitor, the PQ-tree implementation from the OGDF library [Markus Chimani et al., 2014; Leipert, 1997], by a factor of 2 to 4, showing that PC-trees are not only conceptually simpler but also fast in practice. Moreover, we find the Union-Find-based implementation, while having a slightly worse asymptotic runtime, to be twice as fast as the one based on the description by Hsu and McConnell.
Cite as

Simon D. Fink, Matthias Pfretzschner, and Ignaz Rutter. Experimental Comparison of PC-Trees and PQ-Trees. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.ESA.2021.43,
  author =	{Fink, Simon D. and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Experimental Comparison of PC-Trees and PQ-Trees}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.43},
  URN =		{urn:nbn:de:0030-drops-146245},
  doi =		{10.4230/LIPIcs.ESA.2021.43},
  annote =	{Keywords: PQ-Tree, PC-Tree, circular consecutive ones, implementation, experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.55
Polygon-Universal Graphs

Authors: Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek

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

Abstract
We study a fundamental question from graph drawing: given a pair (G,C) of a graph G and a cycle C in G together with a simple polygon P, is there a straight-line drawing of G inside P which maps C to P? We say that such a drawing of (G,C) respects P. We fully characterize those instances (G,C) which are polygon-universal, that is, they have a drawing that respects P for any simple (not necessarily convex) polygon P. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance (G,C) is planar, that is, if there exists a planar drawing of G with C on the outer face, we show that the same conditions guarantee for every simple polygon P the existence of a planar drawing of (G,C) that respects P. If (G,C) is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon P.
Cite as

Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek. Polygon-Universal Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ophelders_et_al:LIPIcs.SoCG.2021.55,
  author =	{Ophelders, Tim and Rutter, Ignaz and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Polygon-Universal Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{55:1--55:15},
  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.55},
  URN =		{urn:nbn:de:0030-drops-138540},
  doi =		{10.4230/LIPIcs.SoCG.2021.55},
  annote =	{Keywords: Graph drawing, partial drawing extension, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.8
An SPQR-Tree-Like Embedding Representation for Level Planarity

Authors: Guido Brückner and Ignaz Rutter

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algorithms, which seek a planar embedding of a graph subject to some given set of constraints. We develop an SPQR-tree-like data structure that represents all level-planar embeddings of a biconnected level graph with a single source, called the LP-tree, and give a simple algorithm to compute it in linear time. Moreover, we show that LP-trees can be used to adapt three constrained planarity algorithms to the level-planar case by using them as a drop-in replacement for SPQR-trees.
Cite as

Guido Brückner and Ignaz Rutter. An SPQR-Tree-Like Embedding Representation for Level Planarity. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bruckner_et_al:LIPIcs.ISAAC.2020.8,
  author =	{Br\"{u}ckner, Guido and Rutter, Ignaz},
  title =	{{An SPQR-Tree-Like Embedding Representation for Level Planarity}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.8},
  URN =		{urn:nbn:de:0030-drops-133526},
  doi =		{10.4230/LIPIcs.ISAAC.2020.8},
  annote =	{Keywords: SPQR-tree, Level planarity, Partial drawings, Simultaneous drawings}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.76
Geometric Crossing-Minimization - A Scalable Randomized Approach

Authors: Marcel Radermacher and Ignaz Rutter

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We consider the minimization of edge-crossings in geometric drawings of graphs G=(V, E), i.e., in drawings where each edge is depicted as a line segment. The respective decision problem is NP-hard [Daniel Bienstock, 1991]. Crossing-minimization, in general, is a popular theoretical research topic; see Vrt'o [Imrich Vrt'o, 2014]. In contrast to theory and the topological setting, the geometric setting did not receive a lot of attention in practice. Prior work [Marcel Radermacher et al., 2018] is limited to the crossing-minimization in geometric graphs with less than 200 edges. The described heuristics base on the primitive operation of moving a single vertex v to its crossing-minimal position, i.e., the position in R^2 that minimizes the number of crossings on edges incident to v. In this paper, we introduce a technique to speed-up the computation by a factor of 20. This is necessary but not sufficient to cope with graphs with a few thousand edges. In order to handle larger graphs, we drop the condition that each vertex v has to be moved to its crossing-minimal position and compute a position that is only optimal with respect to a small random subset of the edges. In our theoretical contribution, we consider drawings that contain for each edge uv in E and each position p in R^2 for v o(|E|) crossings. In this case, we prove that with a random subset of the edges of size Theta(k log k) the co-crossing number of a degree-k vertex v, i.e., the number of edge pairs uv in E, e in E that do not cross, can be approximated by an arbitrary but fixed factor delta with high probability. In our experimental evaluation, we show that the randomized approach reduces the number of crossings in graphs with up to 13 000 edges considerably. The evaluation suggests that depending on the degree-distribution different strategies result in the fewest number of crossings.
Cite as

Marcel Radermacher and Ignaz Rutter. Geometric Crossing-Minimization - A Scalable Randomized Approach. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{radermacher_et_al:LIPIcs.ESA.2019.76,
  author =	{Radermacher, Marcel and Rutter, Ignaz},
  title =	{{Geometric Crossing-Minimization - A Scalable Randomized Approach}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{76:1--76:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.76},
  URN =		{urn:nbn:de:0030-drops-111977},
  doi =		{10.4230/LIPIcs.ESA.2019.76},
  annote =	{Keywords: Geometric Crossing Minimization, Randomization, Approximation, VC-Dimension, Experiments}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.80
Simultaneous Representation of Proper and Unit Interval Graphs

Authors: Ignaz Rutter, Darren Strash, Peter Stumpf, and Michael Vollmer

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs - the simultaneous version of arguably one of the most well-studied graph classes - is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more "rigid" and therefore have less freedom in their representation. We show they can be recognized in time O(|V|*|E|) for any number of simultaneous graphs in the sunflower case where G=(V,E) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.
Cite as

Ignaz Rutter, Darren Strash, Peter Stumpf, and Michael Vollmer. Simultaneous Representation of Proper and Unit Interval Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 80:1-80:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rutter_et_al:LIPIcs.ESA.2019.80,
  author =	{Rutter, Ignaz and Strash, Darren and Stumpf, Peter and Vollmer, Michael},
  title =	{{Simultaneous Representation of Proper and Unit Interval Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{80:1--80:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.80},
  URN =		{urn:nbn:de:0030-drops-112013},
  doi =		{10.4230/LIPIcs.ESA.2019.80},
  annote =	{Keywords: Intersection Graphs, Recognition Algorithm, Proper/Unit Interval Graphs, Simultaneous Representations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.53
Efficient Algorithms for Ortho-Radial Graph Drawing

Authors: Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. Barth et al. [2017] have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation. In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation. Using further structural insights we speed up the drawing algorithm to quadratic running time.
Cite as

Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Efficient Algorithms for Ortho-Radial Graph Drawing. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{niedermann_et_al:LIPIcs.SoCG.2019.53,
  author =	{Niedermann, Benjamin and Rutter, Ignaz and Wolf, Matthias},
  title =	{{Efficient Algorithms for Ortho-Radial Graph Drawing}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.53},
  URN =		{urn:nbn:de:0030-drops-104572},
  doi =		{10.4230/LIPIcs.SoCG.2019.53},
  annote =	{Keywords: Graph Drawing, Ortho-Radial Graph Drawing, Ortho-Radial Representation, Topology-Shape-Metrics, Efficient Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.41
Approximation Algorithms for Facial Cycles in Planar Embeddings

Authors: Giordano Da Lozzo and Ignaz Rutter

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

Abstract
Consider the following combinatorial problem: Given a planar graph G and a set of simple cycles C in G, find a planar embedding E of G such that the number of cycles in C that bound a face in E is maximized. This problem, called Max Facial C-Cycles, was first studied by Mutzel and Weiskircher [IPCO '99, http://dx.doi.org/10.1007/3-540-48777-8_27) and then proved NP-hard by Woeginger [Oper. Res. Lett., 2002, http://dx.doi.org/10.1016/S0167-6377(02)00119-0]. We establish a tight border of tractability for Max Facial C-Cycles in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that strengthening any of these conditions makes the problem polynomial-time solvable. Our main results are approximation algorithms for Max Facial C-Cycles. Namely, we give a 2-approximation for series-parallel graphs and a (4+epsilon)-approximation for biconnected planar graphs. Remarkably, this provides one of the first approximation algorithms for constrained embedding problems.
Cite as

Giordano Da Lozzo and Ignaz Rutter. Approximation Algorithms for Facial Cycles in Planar Embeddings. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2018.41,
  author =	{Da Lozzo, Giordano and Rutter, Ignaz},
  title =	{{Approximation Algorithms for Facial Cycles in Planar Embeddings}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{41:1--41: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.41},
  URN =		{urn:nbn:de:0030-drops-99895},
  doi =		{10.4230/LIPIcs.ISAAC.2018.41},
  annote =	{Keywords: Planar Embeddings, Facial Cycles, Complexity, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.14
Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings

Authors: Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.
Cite as

Lukas Barth, Benjamin Niedermann, Ignaz Rutter, and Matthias Wolf. Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.SoCG.2017.14,
  author =	{Barth, Lukas and Niedermann, Benjamin and Rutter, Ignaz and Wolf, Matthias},
  title =	{{Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.14},
  URN =		{urn:nbn:de:0030-drops-72234},
  doi =		{10.4230/LIPIcs.SoCG.2017.14},
  annote =	{Keywords: Graph Drawing, Ortho-Radial Drawings, Combinatorial Characterization, Bend Minimization, Topology-Shape-Metrics}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.7
Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths

Authors: Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.
Cite as

Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, and Franziska Wegner. Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{baum_et_al:LIPIcs.ESA.2016.7,
  author =	{Baum, Moritz and Bl\"{a}sius, Thomas and Gemsa, Andreas and Rutter, Ignaz and Wegner, Franziska},
  title =	{{Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.7},
  URN =		{urn:nbn:de:0030-drops-63498},
  doi =		{10.4230/LIPIcs.ESA.2016.7},
  annote =	{Keywords: isocontours, separating polygons, minimum-link paths}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.5
Linear-Time Recognition of Map Graphs with Outerplanar Witness

Authors: Matthias Mnich, Ignaz Rutter, and Jens M. Schmidt

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
Map graphs generalize planar graphs and were introduced by Chen, Grigni and Papadimitriou [STOC 1998, J.ACM 2002]. They showed that the problem of recognizing map graphs is in NP by proving the existence of a planar witness graph W. Shortly after, Thorup [FOCS 1998] published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be Omega(n^{120}) for n-vertex graphs, and a full description of its details remains unpublished. We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n+m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.
Cite as

Matthias Mnich, Ignaz Rutter, and Jens M. Schmidt. Linear-Time Recognition of Map Graphs with Outerplanar Witness. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mnich_et_al:LIPIcs.SWAT.2016.5,
  author =	{Mnich, Matthias and Rutter, Ignaz and Schmidt, Jens M.},
  title =	{{Linear-Time Recognition of Map Graphs with Outerplanar Witness}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.5},
  URN =		{urn:nbn:de:0030-drops-60349},
  doi =		{10.4230/LIPIcs.SWAT.2016.5},
  annote =	{Keywords: Algorithms and data structures, map graphs, recognition, planar graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.226
Online Dynamic Power Management with Hard Real-Time Guarantees

Authors: Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59. Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm.
Cite as

Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner. Online Dynamic Power Management with Hard Real-Time Guarantees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 226-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2014.226,
  author =	{Chen, Jian-Jia and Kao, Mong-Jen and Lee, D.T. and Rutter, Ignaz and Wagner, Dorothea},
  title =	{{Online Dynamic Power Management with Hard Real-Time Guarantees}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{226--238},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.226},
  URN =		{urn:nbn:de:0030-drops-44607},
  doi =		{10.4230/LIPIcs.STACS.2014.226},
  annote =	{Keywords: Energy-Efficient Scheduling, Online Dynamic Power Management}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.71
On the Complexity of Partitioning Graphs for Arc-Flags

Authors: Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
Precomputation of auxiliary data in an additional off-line step is a common approach towards improving the performance of shortest-path queries in large-scale networks. One such technique is the arc-flags algorithm, where the preprocessing involves computing a partition of the input graph. The quality of this partition significantly affects the speed-up observed in the query phase. It is evaluated by considering the search-space size of subsequent shortest-path queries, in particular its maximum or its average over all queries. In this paper, we substantially strengthen existing hardness results of Bauer et al. and show that optimally filling this degree of freedom is NP-hard for trees with unit-length edges, even if we bound the height or the degree. On the other hand, we show that optimal partitions for paths can be computed efficiently and give approximation algorithms for cycles and trees.
Cite as

Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner. On the Complexity of Partitioning Graphs for Arc-Flags. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.ATMOS.2012.71,
  author =	{Bauer, Reinhard and Baum, Moritz and Rutter, Ignaz and Wagner, Dorothea},
  title =	{{On the Complexity of Partitioning Graphs for Arc-Flags}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{71--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.71},
  URN =		{urn:nbn:de:0030-drops-37048},
  doi =		{10.4230/OASIcs.ATMOS.2012.71},
  annote =	{Keywords: shortest paths, arc-flags, search space, preprocessing, complexity}
}
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