Search Results

Documents authored by Fink, Simon D.

Document
DOI: 10.4230/LIPIcs.GD.2025.4
Heuristics for Exact 1-Planarity Testing

Authors: Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter

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

Abstract
Since many real-world graphs are nonplanar, the study of graphs that allow few crossings per edge has been an active subfield of graph theory in recent years. One of the most natural generalizations of planar graphs are the so-called 1-planar graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing whether a graph is 1-planar is known to be NP-complete even for very restricted graph classes. On the positive side, Binucci, Didimo and Montecchiani [Binucci et al., 2023] presented the first practical algorithm for testing 1-planarity based on an easy-to-implement backtracking strategy. We build on this idea and systematically explore the design choices of such algorithms and propose several new ingredients, such as different branching strategies and multiple filter criteria that allow us to reject certain branches in the search tree early on. We conduct an extensive experimental evaluation that evaluates the efficiency and effectiveness of these ingredients. Given a time limit of three hours per instance, our best configuration is able to solve more than 95% of the non-planar instances from the well-known North and Rome graphs with up to 50 vertices. Notably, the median running time for solved instances is well below 4 seconds.
Cite as

Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter. Heuristics for Exact 1-Planarity Testing. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.GD.2025.4,
  author =	{Fink, Simon D. and M\"{u}nch, Miriam and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Heuristics for Exact 1-Planarity Testing}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.4},
  URN =		{urn:nbn:de:0030-drops-249909},
  doi =		{10.4230/LIPIcs.GD.2025.4},
  annote =	{Keywords: 1-Planarity, Experiments, Backtracking}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.15
Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms

Authors: Thomas Depian, Simon D. Fink, Robert Ganian, and Vaishali Surianarayanan

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

Abstract
In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layouts. A stack (resp. queue) layout places vertices along a line and assigns edges to pages so that no two edges on the same page are crossing (resp. nested). We provide three new algorithms which together substantially expand our understanding of these problems: 1) A fixed-parameter algorithm for computing minimum-page stack and queue layouts w.r.t. the vertex integrity of an n-vertex graph G. This result is motivated by an open question in the literature and generalizes the previous algorithms parameterizing by the vertex cover number of G. The proof relies on a newly developed Ramsey pruning technique. Vertex integrity intuitively measures the vertex deletion distance to a subgraph with only small connected components. 2) An n^𝒪(q 𝓁) algorithm for computing 𝓁-page stack and queue layouts of page width at most q. This is the first algorithm avoiding a double-exponential dependency on the parameters. The page width of a layout measures the maximum number of edges one needs to cross on any page to reach the outer face. 3) A 2^𝒪(n) algorithm for computing 1-page queue layouts. This improves upon the previously fastest n^𝒪(n) algorithm and can be seen as a counterpart to the recent subexponential algorithm for computing 2-page stack layouts [ICALP'24], but relies on an entirely different technique.
Cite as

Thomas Depian, Simon D. Fink, Robert Ganian, and Vaishali Surianarayanan. Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ESA.2025.15,
  author =	{Depian, Thomas and Fink, Simon D. and Ganian, Robert and Surianarayanan, Vaishali},
  title =	{{Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.15},
  URN =		{urn:nbn:de:0030-drops-244835},
  doi =		{10.4230/LIPIcs.ESA.2025.15},
  annote =	{Keywords: stack layouts, queue layouts, parameterized algorithms, vertex integrity, Ramsey theory}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.84
Incremental and Interactive PQ- and PC-Trees (Media Exposition)

Authors: Simon D. Fink and Dominik Peters

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
PQ-trees [Booth, 1975; Kellogg S. Booth and George S. Lueker, 1976] (and their more general variant PC-trees [Hsu and McConnell, 2003; Wei-Kuan and Wen-Lian, 1999]) are a well-known data structure for representing the set of linear (or for PC-trees, circular) orders respecting a given set of consecutivity constraints. Each such constraint is specified by a set of elements and requires that these elements appear consecutively in the linear (or circular) order; thus, they disallow the set to be interleaved with its complement. The main operation supported by these data structures is thus the so-called update, which takes as input a set that forms an additional constraint, and in response changes the tree in order to restrict the represented orders to those satisfying the new constraint. Interpreting a given tree is straightforward: leaves represent the underlying elements, while inner nodes either allow the order of their subtrees to be reversed (Q/C-nodes) or to be arbitrarily permuted (P-nodes). However, the way this structure and the set of represented orders change under updates is less intuitive. We present an interactive web app that allows users to specify sets of consecutivity constraints in the form of a 0/1-matrix and then calculates and visualizes the corresponding PQ- or PC-tree. The constraints can then be changed dynamically while observing how this changes the structure of the tree and the set of represented orders. Through this interactive exploration, we hope to make PQ- and PC-trees more accessible to a wider audience.
Cite as

Simon D. Fink and Dominik Peters. Incremental and Interactive PQ- and PC-Trees (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 84:1-84:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.SoCG.2025.84,
  author =	{Fink, Simon D. and Peters, Dominik},
  title =	{{Incremental and Interactive PQ- and PC-Trees}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{84:1--84:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.84},
  URN =		{urn:nbn:de:0030-drops-232365},
  doi =		{10.4230/LIPIcs.SoCG.2025.84},
  annote =	{Keywords: PQ trees, PC trees, planarity, consecutive ones problem, interactive exploration}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.12
The Parameterized Complexity Of Extending Stack Layouts

Authors: Thomas Depian, Simon D. Fink, Robert Ganian, and Martin Nöllenburg

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

Abstract
An 𝓁-page stack layout (also known as an 𝓁-page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into 𝓁 stacks (or pages), such that the endpoints of no two edges on the same stack alternate. We study the problem of extending a given partial 𝓁-page stack layout into a complete one, which can be seen as a natural generalization of the classical NP-hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. Our results paint a detailed and surprisingly rich complexity-theoretic landscape of the problem which includes the identification of paraNP-hard, W[1]-hard and XP-tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations.
Cite as

Thomas Depian, Simon D. Fink, Robert Ganian, and Martin Nöllenburg. The Parameterized Complexity Of Extending Stack Layouts. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.GD.2024.12,
  author =	{Depian, Thomas and Fink, Simon D. and Ganian, Robert and N\"{o}llenburg, Martin},
  title =	{{The Parameterized Complexity Of Extending Stack Layouts}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.12},
  URN =		{urn:nbn:de:0030-drops-212960},
  doi =		{10.4230/LIPIcs.GD.2024.12},
  annote =	{Keywords: Stack Layout, Drawing Extension, Parameterized Complexity, Book Embedding}
}
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.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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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