Search Results

Documents authored by Münch, Miriam

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}
}
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 About DROPS Imprint Privacy Contact