4 Search Results for "Di Giacomo, Emilio"

Document
DOI: 10.4230/LIPIcs.SoCG.2022.26
Parameterized Algorithms for Upward Planarity

Authors: Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, and Kirill Simonov

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.
Cite as

Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, and Kirill Simonov. Parameterized Algorithms for Upward Planarity. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 26:1-26:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.SoCG.2022.26,
  author =	{Chaplick, Steven and Di Giacomo, Emilio and Frati, Fabrizio and Ganian, Robert and Raftopoulou, Chrysanthi N. and Simonov, Kirill},
  title =	{{Parameterized Algorithms for Upward Planarity}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.26},
  URN =		{urn:nbn:de:0030-drops-160349},
  doi =		{10.4230/LIPIcs.SoCG.2022.26},
  annote =	{Keywords: Upward planarity, parameterized algorithms, SPQR trees, treewidth, treedepth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.53
On Compact RAC Drawings

Authors: Henry Förster and Michael Kaufmann

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We present new bounds for the required area of Right Angle Crossing (RAC) drawings for complete graphs, i.e. drawings where any two crossing edges are perpendicular to each other. First, we improve upon results by Didimo et al. [Walter Didimo et al., 2011] and Di Giacomo et al. [Emilio Di Giacomo et al., 2011] by showing how to compute a RAC drawing with three bends per edge in cubic area. We also show that quadratic area can be achieved when allowing eight bends per edge in general or with three bends per edge for p-partite graphs. As a counterpart, we prove that in general quadratic area is not sufficient for RAC drawings with three bends per edge.
Cite as

Henry Förster and Michael Kaufmann. On Compact RAC Drawings. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 53:1-53:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.ESA.2020.53,
  author =	{F\"{o}rster, Henry and Kaufmann, Michael},
  title =	{{On Compact RAC Drawings}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.53},
  URN =		{urn:nbn:de:0030-drops-129192},
  doi =		{10.4230/LIPIcs.ESA.2020.53},
  annote =	{Keywords: RAC drawings, visualization of dense graphs, compact drawings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.13
Upward Book Embeddings of st-Graphs

Authors: Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo, Walter Didimo, Tamara Mchedlidze, and Maurizio Patrignani

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We study k-page upward book embeddings (kUBEs) of st-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on k pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a kUBE is NP-complete for k >= 3. A hardness result for this problem was previously known only for k = 6 [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on k=2. On the algorithmic side, we present polynomial-time algorithms for testing the existence of 2UBEs of planar st-graphs with branchwidth b and of plane st-graphs whose faces have a special structure. These algorithms run in O(f(b)* n+n^3) time and O(n) time, respectively, where f is a singly-exponential function on b. Moreover, on the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2UBE.
Cite as

Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo, Walter Didimo, Tamara Mchedlidze, and Maurizio Patrignani. Upward Book Embeddings of st-Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 13:1-13:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.SoCG.2019.13,
  author =	{Binucci, Carla and Da Lozzo, Giordano and Di Giacomo, Emilio and Didimo, Walter and Mchedlidze, Tamara and Patrignani, Maurizio},
  title =	{{Upward Book Embeddings of st-Graphs}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.13},
  URN =		{urn:nbn:de:0030-drops-104170},
  doi =		{10.4230/LIPIcs.SoCG.2019.13},
  annote =	{Keywords: Upward Book Embeddings, st-Graphs, SPQR-trees, Branchwidth, Sphere-cut Decomposition}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.39
Polyline Drawings with Topological Constraints

Authors: Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Henk Meijer, and Fabrizio Montecchiani

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Let G be a simple topological graph and let Gamma be a polyline drawing of G. We say that Gamma partially preserves the topology of G if it has the same external boundary, the same rotation system, and the same set of crossings as G. Drawing Gamma fully preserves the topology of G if the planarization of G and the planarization of Gamma have the same planar embedding. We show that if the set of crossing-free edges of G forms a connected spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Omega(sqrt{n}). Concerning drawings that fully preserve the topology, we show that if G has skewness k, it admits one such drawing with curve complexity at most 2k; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.
Cite as

Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Henk Meijer, and Fabrizio Montecchiani. Polyline Drawings with Topological Constraints. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 39:1-39:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{digiacomo_et_al:LIPIcs.ISAAC.2018.39,
  author =	{Di Giacomo, Emilio and Eades, Peter and Liotta, Giuseppe and Meijer, Henk and Montecchiani, Fabrizio},
  title =	{{Polyline Drawings with Topological Constraints}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{39:1--39:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.39},
  URN =		{urn:nbn:de:0030-drops-99871},
  doi =		{10.4230/LIPIcs.ISAAC.2018.39},
  annote =	{Keywords: Topological graphs, graph drawing, curve complexity, skewness-k graphs, k-planar graphs}
}
  • Refine by Author
  • 3 Di Giacomo, Emilio
  • 1 Binucci, Carla
  • 1 Chaplick, Steven
  • 1 Da Lozzo, Giordano
  • 1 Didimo, Walter
  • Show More...

  • Refine by Classification
  • 2 Human-centered computing → Graph drawings
  • 2 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Graphs and surfaces
  • Show More...

  • Refine by Keyword
  • 1 Branchwidth
  • 1 RAC drawings
  • 1 SPQR trees
  • 1 SPQR-trees
  • 1 Sphere-cut Decomposition
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019
  • 1 2020
  • 1 2022

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact