18 Search Results for "Rutter, Ignaz"

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.26
Rectilinear-Upward Planarity Testing of Digraphs

Authors: Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali, and Maurizio Patrignani

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

Abstract
A rectilinear-upward planar drawing of a digraph G is a crossing-free drawing of G where each edge is either a horizontal or a vertical segment, and such that no directed edge points downward. Rectilinear-Upward Planarity Testing is the problem of deciding whether a digraph G admits a rectilinear-upward planar drawing. We show that: (i) Rectilinear-Upward Planarity Testing is NP-complete, even if G is biconnected; (ii) it can be solved in linear time when an upward planar embedding of G is fixed; (iii) the problem is polynomial-time solvable for biconnected digraphs of treewidth at most two, i.e., for digraphs whose underlying undirected graph is a series-parallel graph; (iv) for any biconnected digraph the problem is fixed-parameter tractable when parameterized by the number of sources and sinks in the digraph.
Cite as

Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali, and Maurizio Patrignani. Rectilinear-Upward Planarity Testing of Digraphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 26:1-26:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{didimo_et_al:LIPIcs.ISAAC.2023.26,
  author =	{Didimo, Walter and Kaufmann, Michael and Liotta, Giuseppe and Ortali, Giacomo and Patrignani, Maurizio},
  title =	{{Rectilinear-Upward Planarity Testing of Digraphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.26},
  URN =		{urn:nbn:de:0030-drops-193283},
  doi =		{10.4230/LIPIcs.ISAAC.2023.26},
  annote =	{Keywords: Graph drawing, orthogonal drawings, upward drawings, rectilinear planarity, upward planarity}
}
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}
}
  • Refine by Author
  • 17 Rutter, Ignaz
  • 4 Stumpf, Peter
  • 2 Baum, Moritz
  • 2 Bläsius, Thomas
  • 2 Brückner, Guido
  • Show More...

  • Refine by Classification
  • 5 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Human-centered computing → Graph drawings
  • 2 Mathematics of computing → Permutations and combinations
  • Show More...

  • Refine by Keyword
  • 2 Graph Drawing
  • 2 Graph drawing
  • 2 Topology-Shape-Metrics
  • 1 Algorithms and data structures
  • 1 Approximation
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 4 2021
  • 3 2019
  • 2 2016
  • 2 2022
  • 2 2023
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact