Search Results

Documents authored by Di Battista, Giuseppe

Document
DOI: 10.4230/LIPIcs.GD.2024.20
Quantum Algorithms for One-Sided Crossing Minimization

Authors: Susanna Caroppo, Giordano Da Lozzo, and Giuseppe Di Battista

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

Abstract
We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. We show that OSCM can be viewed as a set problem amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA 2019] to devise a QRAM-based algorithm that solves OSCM in 𝒪^*(1.728ⁿ) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in 𝒪^*(2ⁿ) time and polynomial space.
Cite as

Susanna Caroppo, Giordano Da Lozzo, and Giuseppe Di Battista. Quantum Algorithms for One-Sided Crossing Minimization. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 20:1-20:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{caroppo_et_al:LIPIcs.GD.2024.20,
  author =	{Caroppo, Susanna and Da Lozzo, Giordano and Di Battista, Giuseppe},
  title =	{{Quantum Algorithms for One-Sided Crossing Minimization}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{20:1--20:9},
  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.20},
  URN =		{urn:nbn:de:0030-drops-213045},
  doi =		{10.4230/LIPIcs.GD.2024.20},
  annote =	{Keywords: One-sided crossing minimization, quantum graph drawing, quantum dynamic programming, quantum divide and conquer, exact exponential algorithms}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.24
Upward Pointset Embeddings of Planar st-Graphs

Authors: Carlos Alegría, Susanna Caroppo, Giordano Da Lozzo, Marco D'Elia, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso, and Maurizio Patrignani

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

Abstract
We study upward pointset embeddings (UPSEs) of planar st-graphs. Let G be a planar st-graph and let S ⊂ ℝ² be a pointset with |S| = |V(G)|. An UPSE of G on S is an upward planar straight-line drawing of G that maps the vertices of G to the points of S. We consider both the problem of testing the existence of an UPSE of G on S (UPSE Testing) and the problem of enumerating all UPSEs of G on S. We prove that UPSE Testing is NP-complete even for st-graphs that consist of a set of directed st-paths sharing only s and t. On the other hand, for n-vertex planar st-graphs whose maximum st-cutset has size k, we prove that it is possible to solve UPSE Testing in 𝒪(n^{4k}) time with 𝒪(n^{3k}) space, and to enumerate all UPSEs of G on S with 𝒪(n) worst-case delay, using 𝒪(k n^{4k} log n) space, after 𝒪(k n^{4k} log n) set-up time. Moreover, for an n-vertex st-graph whose underlying graph is a cycle, we provide a necessary and sufficient condition for the existence of an UPSE on a given poinset, which can be tested in 𝒪(n log n) time. Related to this result, we give an algorithm that, for a set S of n points, enumerates all the non-crossing monotone Hamiltonian cycles on S with 𝒪(n) worst-case delay, using 𝒪(n²) space, after 𝒪(n²) set-up time.
Cite as

Carlos Alegría, Susanna Caroppo, Giordano Da Lozzo, Marco D'Elia, Giuseppe Di Battista, Fabrizio Frati, Fabrizio Grosso, and Maurizio Patrignani. Upward Pointset Embeddings of Planar st-Graphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alegria_et_al:LIPIcs.GD.2024.24,
  author =	{Alegr{\'\i}a, Carlos and Caroppo, Susanna and Da Lozzo, Giordano and D'Elia, Marco and Di Battista, Giuseppe and Frati, Fabrizio and Grosso, Fabrizio and Patrignani, Maurizio},
  title =	{{Upward Pointset Embeddings of Planar st-Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{24:1--24:18},
  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.24},
  URN =		{urn:nbn:de:0030-drops-213082},
  doi =		{10.4230/LIPIcs.GD.2024.24},
  annote =	{Keywords: Upward pointset embeddings, planar st-graphs, st-cutset, non-crossing monotone Hamiltonian cycles, graph drawing enumeration}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.32
On the Complexity of Recognizing k^+-Real Face Graphs

Authors: Michael A. Bekos, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Michael Kaufmann, and Fabrizio Montecchiani

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

Abstract
A nonplanar drawing Γ of a graph G divides the plane into topologically connected regions, called faces (or cells). The boundary of each face is formed by vertices, crossings, and edge segments. Given a positive integer k, we say that Γ is a k^+-real face drawing of G if the boundary of each face of Γ contains at least k vertices of G. The study of k^+-real face drawings started in a paper by Binucci et al. (WG 2023), where edge density bounds and relationships with other beyond-planar graph classes are proved. In this paper, we investigate the complexity of recognizing k^+-real face graphs, i.e., graphs that admit a k^+-real face drawing. We study both the general unconstrained scenario and the 2-layer scenario in which the graph is bipartite, the vertices of the two partition sets lie on two distinct horizontal layers, and the edges are straight-line segments. We give NP-completeness results for the unconstrained scenario and efficient recognition algorithms for the 2-layer setting.
Cite as

Michael A. Bekos, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Michael Kaufmann, and Fabrizio Montecchiani. On the Complexity of Recognizing k^+-Real Face Graphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2024.32,
  author =	{Bekos, Michael A. and Di Battista, Giuseppe and Di Giacomo, Emilio and Didimo, Walter and Kaufmann, Michael and Montecchiani, Fabrizio},
  title =	{{On the Complexity of Recognizing k^+-Real Face Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{32:1--32:22},
  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.32},
  URN =		{urn:nbn:de:0030-drops-213167},
  doi =		{10.4230/LIPIcs.GD.2024.32},
  annote =	{Keywords: Beyond planarity, k^+-real face drawings, 2-layer drawings, recognition algorithm, NP-hardness}
}
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