11 Search Results for "Münch, Miriam"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.16
A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

Authors: Sergio Cabello, Alexander Dobler, Gašper Fijavž, Thekla Hamm, and Mirko H. Wagner

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
A drawing of a graph is 1-planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a 1-planar drawing belongs to one out of six possible crossing types, where a type characterizes the subgraph induced by the four vertices of the crossing edges. Each of the 63 possible nonempty subsets 𝒮 of crossing types gives a recognition problem: does a given graph admit an 𝒮-restricted drawing, that is, a 1-planar drawing where the crossing type of each crossing is in 𝒮? We show that there is a set 𝒮_bad with three crossing types and the following properties: - If 𝒮 contains no crossing type from 𝒮_bad, then the recognition of graphs that admit an 𝒮-restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph. - If 𝒮 contains any crossing type from 𝒮_bad, then it is NP-hard to decide whether a graph has an 𝒮-restricted drawing, even when considering graphs of constant pathwidth. We also extend this characterization of crossing types to 1-planar straight-line drawings and show the same complexity behaviour parameterized by treewidth.
Cite as

Sergio Cabello, Alexander Dobler, Gašper Fijavž, Thekla Hamm, and Mirko H. Wagner. A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ISAAC.2025.16,
  author =	{Cabello, Sergio and Dobler, Alexander and Fijav\v{z}, Ga\v{s}per and Hamm, Thekla and Wagner, Mirko H.},
  title =	{{A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.16},
  URN =		{urn:nbn:de:0030-drops-249248},
  doi =		{10.4230/LIPIcs.ISAAC.2025.16},
  annote =	{Keywords: 1-planar, crossing type, treewidth, pathwidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.25
Structural Parameterizations of Simultaneous Planarity

Authors: Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Given a set of graphs on the same vertex set, the problem Simultaneous Embedding With Fixed Edges (SEFE) asks, whether there exist planar drawings of all input graphs, such that every pair of drawings coincides on their shared subgraph. It is known that SEFE is NP-complete [Elisabeth Gassner et al., 2006], even in the so-called sunflower case, where all pairs of input graphs have the same shared graph G_∩ [Marcus Schaefer, 2012]. Fink, Pfretzschner, and Rutter [Simon D. Fink et al., 2023] recently initiated the study of the parameterized complexity of SEFE in the sunflower case, mainly focusing on structural parameters of G_∩. In this work, we shift the focus towards parameters of the union graph G_∪ that contains the edges of all input graphs. On the positive side, we establish fixed-parameter tractability for the problem with respect to the feedback edge set number of G_∪. We complement this result by showing that it, surprisingly, remains NP-complete even if G_∪ has constant vertex cover number. These results settle two open questions posed by Fink et al. [Simon D. Fink et al., 2023].
Cite as

Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter. Structural Parameterizations of Simultaneous Planarity. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ISAAC.2025.25,
  author =	{Depian, Thomas and Fink, Simon D. and Firbas, Alexander and Ganian, Robert and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Structural Parameterizations of Simultaneous Planarity}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.25},
  URN =		{urn:nbn:de:0030-drops-249332},
  doi =		{10.4230/LIPIcs.ISAAC.2025.25},
  annote =	{Keywords: SEFE, Simultaneous Planarity, Fixed-Parameter Tractability, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.24
String Graph Obstacles of High Girth and of Bounded Degree

Authors: Maria Chudnovsky, David Eppstein, and David Fischer

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

Abstract
A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for which any edge contraction or vertex deletion produces a string graph. Kratochvíl’s obstacles contain arbitrarily large cliques, so they have girth three and unbounded degree. We extend this line of working by studying obstacles among graphs of restricted girth and/or degree. We construct an infinite family of obstacles of girth four; in addition, our construction is K_{2,3}-subgraph-free and near-planar (planar plus one edge). Furthermore, we prove that there is a subcubic obstacle of girth three, and that there are no subcubic obstacles of high girth. We characterize the subcubic string graphs as having a matching whose contraction yields a planar graph, and based on this characterization we find a linear-time algorithm for recognizing subcubic string graphs of bounded treewidth.
Cite as

Maria Chudnovsky, David Eppstein, and David Fischer. String Graph Obstacles of High Girth and of Bounded Degree. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.GD.2025.24,
  author =	{Chudnovsky, Maria and Eppstein, David and Fischer, David},
  title =	{{String Graph Obstacles of High Girth and of Bounded Degree}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{24:1--24:18},
  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.24},
  URN =		{urn:nbn:de:0030-drops-250108},
  doi =		{10.4230/LIPIcs.GD.2025.24},
  annote =	{Keywords: string graphs, induced minors, forbidden minors, sparsity, triangle-free graphs, near-planar graphs}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.50
Reeb Lobsters Are 1-Planar (Poster Abstract)

Authors: Maarten Löffler, Miriam Münch, and Ignaz Rutter

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

Abstract
Very recently, Chambers, Fasy, Hosseini Sereshgi and Löffler [Erin W. Chambers et al., 2025] showed that every Reeb caterpillar admits a crossing-free drawing. It turns out that this does not hold for Reeb lobsters but we show that these graphs admit drawings with at most one crossing per edge.
Cite as

Maarten Löffler, Miriam Münch, and Ignaz Rutter. Reeb Lobsters Are 1-Planar (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 50:1-50:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.GD.2025.50,
  author =	{L\"{o}ffler, Maarten and M\"{u}nch, Miriam and Rutter, Ignaz},
  title =	{{Reeb Lobsters Are 1-Planar}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{50:1--50:5},
  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.50},
  URN =		{urn:nbn:de:0030-drops-250365},
  doi =		{10.4230/LIPIcs.GD.2025.50},
  annote =	{Keywords: Reeb graphs, layered drawings, local crossing number}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.16
Structural Parameterizations of k-Planarity

Authors: Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada

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

Abstract
The concept of k-planarity is extensively studied in the context of Beyond Planarity. A graph is k-planar if it admits a drawing in the plane in which each edge is crossed at most k times. The local crossing number of a graph is the minimum integer k such that it is k-planar. The problem of determining whether an input graph is 1-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor 2 - ε for any ε > 0 [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of k = 1, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case k ≥ 1 and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing 1-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most 2.
Cite as

Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada. Structural Parameterizations of k-Planarity. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.GD.2025.16,
  author =	{Gima, Tatsuya and Kobayashi, Yasuaki and Okada, Yuto},
  title =	{{Structural Parameterizations of k-Planarity}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{16:1--16:17},
  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.16},
  URN =		{urn:nbn:de:0030-drops-250021},
  doi =		{10.4230/LIPIcs.GD.2025.16},
  annote =	{Keywords: 1-planar graphs, local crossing number, beyond planarity, parameterized complexity, kernelization}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.14
OOPS: Optimized One-Planarity Solver via SAT

Authors: Sergey Pupyrev

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

Abstract
We present OOPS (Optimized One-Planarity Solver), a practical heuristic for recognizing 1-planar graphs and several important subclasses. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once - a natural generalization of planar graphs that has received increasing attention in graph drawing and beyond-planar graph theory. Although testing planarity can be done in linear time, recognizing 1-planar graphs is NP-complete, making effective practical algorithms especially valuable. The core idea of our approach is to reduce the recognition of 1-planarity to a propositional satisfiability (SAT) instance, enabling the use of modern SAT solvers to efficiently explore the search space. Despite the inherent complexity of the problem, our method is substantially faster in practice than naïve or brute-force algorithms. In addition to demonstrating the empirical performance of our solver on synthetic and real-world instances, we show how OOPS can be used as a discovery tool in theoretical graph theory. Specifically, we employ OOPS to investigate two research problems concerning 1-planarity of specific graph families. Our implementation of the algorithm is publicly available to support further exploration in the field.
Cite as

Sergey Pupyrev. OOPS: Optimized One-Planarity Solver via SAT. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pupyrev:LIPIcs.GD.2025.14,
  author =	{Pupyrev, Sergey},
  title =	{{OOPS: Optimized One-Planarity Solver via SAT}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-250004},
  doi =		{10.4230/LIPIcs.GD.2025.14},
  annote =	{Keywords: beyond planarity, 1-planar graph, SAT, book embeddings, upward 1-planarity}
}
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.21
A Unified FPT Framework for Crossing Number Problems

Authors: Éric Colin de Verdière and Petr Hliněný

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

Abstract
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to ℤ_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.
Cite as

Éric Colin de Verdière and Petr Hliněný. A Unified FPT Framework for Crossing Number Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2025.21,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Hlin\v{e}n\'{y}, Petr},
  title =	{{A Unified FPT Framework for Crossing Number Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-244897},
  doi =		{10.4230/LIPIcs.ESA.2025.21},
  annote =	{Keywords: computational geometry, fixed-parameter tractability, graph drawing, graph embedding, crossing number, two-dimensional simplicial complex, surface}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.23
Simple Realizability of Abstract Topological Graphs

Authors: Giordano Da Lozzo, Walter Didimo, Fabrizio Montecchiani, Miriam Münch, Maurizio Patrignani, and Ignaz Rutter

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
An abstract topological graph (AT-graph) is a pair A = (G, X), where G = (V,E) is a graph and X ⊆ binom(E,2) is a set of pairs of edges of G. A realization of A is a drawing Γ_A of G in the plane such that any two edges e₁,e₂ of G cross in Γ_A if and only if (e₁,e₂) ∈ X; Γ_A is simple if any two edges intersect at most once (either at a common endpoint or at a proper crossing). The AT-graph Realizability (ATR) problem asks whether an input AT-graph admits a realization. The version of this problem that requires a simple realization is called Simple AT-graph Realizability (SATR). It is a classical result that both ATR and SATR are NP-complete [Kratochvíl, 1991; Kratochvíl and Matoušek, 1989]. In this paper, we study the SATR problem from a new structural perspective. More precisely, we consider the size λ(A) of the largest connected component of the crossing graph of any realization of A, i.e., the graph C(A) = (E, X). This parameter represents a natural way to measure the level of interplay among edge crossings. First, we prove that SATR is NP-complete when λ(A) ≥ 6. On the positive side, we give an optimal linear-time algorithm that solves SATR when λ(A) ≤ 3 and returns a simple realization if one exists. Our algorithm is based on several ingredients, in particular the reduction to a new embedding problem subject to constraints that require certain pairs of edges to alternate (in the rotation system), and a sequence of transformations that exploit the interplay between alternation constraints and the SPQR-tree and PQ-tree data structures to eventually arrive at a simpler embedding problem that can be solved with standard techniques.
Cite as

Giordano Da Lozzo, Walter Didimo, Fabrizio Montecchiani, Miriam Münch, Maurizio Patrignani, and Ignaz Rutter. Simple Realizability of Abstract Topological Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2024.23,
  author =	{Da Lozzo, Giordano and Didimo, Walter and Montecchiani, Fabrizio and M\"{u}nch, Miriam and Patrignani, Maurizio and Rutter, Ignaz},
  title =	{{Simple Realizability of Abstract Topological Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.23},
  URN =		{urn:nbn:de:0030-drops-221501},
  doi =		{10.4230/LIPIcs.ISAAC.2024.23},
  annote =	{Keywords: Abstract Topological Graphs, SPQR-Trees, Synchronized PQ-Trees}
}
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.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}
}
  • Refine by Type
  • 11 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 8 2025
  • 2 2024
  • 1 2022

  • Refine by Author
  • 6 Rutter, Ignaz
  • 5 Münch, Miriam
  • 2 Fink, Simon D.
  • 2 Pfretzschner, Matthias
  • 1 Cabello, Sergio
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 4 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Fixed parameter tractability
  • 2 Mathematics of computing → Graph theory
  • 2 Mathematics of computing → Graphs and surfaces
  • Show More...

  • Refine by Keyword
  • 2 beyond planarity
  • 2 local crossing number
  • 1 1-Planarity
  • 1 1-planar
  • 1 1-planar graph
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact