Search Results

Documents authored by Stumpf, Peter

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
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.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}
}
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