Search Results

Documents authored by Da Lozzo, Giordano

Document
DOI: 10.4230/LIPIcs.GD.2024.13
The Price of Upwardness

Authors: Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff

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

Abstract
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k ≥ 1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-k-planarity testing is NP-complete already for k = 1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.
Cite as

Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff. The Price of Upwardness. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.GD.2024.13,
  author =	{Angelini, Patrizio and Biedl, Therese and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Hong, Seok-Hee and Liotta, Giuseppe and Patrignani, Maurizio and Pupyrev, Sergey and Rutter, Ignaz and Wolff, Alexander},
  title =	{{The Price of Upwardness}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{13:1--13:20},
  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.13},
  URN =		{urn:nbn:de:0030-drops-212977},
  doi =		{10.4230/LIPIcs.GD.2024.13},
  annote =	{Keywords: upward drawings, beyond planarity, upward k-planarity, upward outer-1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.19
Weakly Leveled Planarity with Bounded Span

Authors: Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, and Ioannis G. Tollis

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

Abstract
This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly y-monotone curve. A graph is s-span weakly leveled planar if it admits such a drawing where the edges have span at most s; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Θ(log n)-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, and Ioannis G. Tollis. Weakly Leveled Planarity with Bounded Span. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2024.19,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Frati, Fabrizio and Gupta, Siddharth and Kindermann, Philipp and Liotta, Giuseppe and Rutter, Ignaz and Tollis, Ioannis G.},
  title =	{{Weakly Leveled Planarity with Bounded Span}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{19:1--19:19},
  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.19},
  URN =		{urn:nbn:de:0030-drops-213035},
  doi =		{10.4230/LIPIcs.GD.2024.19},
  annote =	{Keywords: Leveled planar graphs, edge span, graph drawing, edge-length ratio}
}
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.ISAAC.2022.23
Graph Product Structure for h-Framed Graphs

Authors: Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size 3⌊ h/2 ⌋+⌊ h/3 ⌋-1. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 115 to 82 and from ⌊ 33/2(k+3 ⌊ k/2⌋ -3)⌋ to ⌊ 33/2 (3⌊ k/2 ⌋+⌊ k/3 ⌋-1) ⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph Product Structure for h-Framed Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.ISAAC.2022.23,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Hlin\v{e}n\'{y}, Petr and Kaufmann, Michael},
  title =	{{Graph Product Structure for h-Framed Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{23:1--23:15},
  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.23},
  URN =		{urn:nbn:de:0030-drops-173086},
  doi =		{10.4230/LIPIcs.ISAAC.2022.23},
  annote =	{Keywords: Graph product structure theory, h-framed graphs, k-map graphs, queue number, twin-width}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.10
On Upward-Planar L-Drawings of Graphs

Authors: Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, and Giordano Da Lozzo

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of e and of a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s,t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but the DAG is biconnected and series-parallel.
Cite as

Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, and Giordano Da Lozzo. On Upward-Planar L-Drawings of Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.MFCS.2022.10,
  author =	{Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano},
  title =	{{On Upward-Planar L-Drawings of Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.10},
  URN =		{urn:nbn:de:0030-drops-168085},
  doi =		{10.4230/LIPIcs.MFCS.2022.10},
  annote =	{Keywords: graph drawing, planar L-drawings, directed graphs, bitonic st-ordering, upward planarity, series-parallel graphs}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.8
Recognizing Map Graphs of Bounded Treewidth

Authors: Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, and Alessandra Tappini

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
A map graph is one admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time complexity that is linear in the size of the graph and, if the input is a yes-instance, it reports a certificate in the form of a so-called witness. Furthermore, this result is developed within a more general algorithmic framework that allows to test, for any k, if the input graph admits a k-map (where at most k nations meet at a common point) or a hole-free k-map (where each point is covered by at least one nation). We point out that, although bounding the treewidth of the input graph also bounds the size of its largest clique, the latter alone does not seem to be a strong enough structural limitation to obtain an efficient time complexity. In fact, while the largest clique in a k-map graph is ⌊ 3k/2 ⌋, the recognition of k-map graphs is still open for any fixed k ≥ 5.
Cite as

Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, and Alessandra Tappini. Recognizing Map Graphs of Bounded Treewidth. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.SWAT.2022.8,
  author =	{Angelini, Patrizio and Bekos, Michael A. and Da Lozzo, Giordano and Gronemann, Martin and Montecchiani, Fabrizio and Tappini, Alessandra},
  title =	{{Recognizing Map Graphs of Bounded Treewidth}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.8},
  URN =		{urn:nbn:de:0030-drops-161681},
  doi =		{10.4230/LIPIcs.SWAT.2022.8},
  annote =	{Keywords: Map graphs, Recognition, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.16
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

Authors: Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou. Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.SoCG.2020.16,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Griesbach, Svenja M. and Gronemann, Martin and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi},
  title =	{{Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.16},
  URN =		{urn:nbn:de:0030-drops-121749},
  doi =		{10.4230/LIPIcs.SoCG.2020.16},
  annote =	{Keywords: Book embeddings, Book thickness, Nonplanar graphs, Planar skeleton}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.9
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width

Authors: Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA'95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT algorithm for embedded clustered graphs, when parameterized by the carving-width of the dual graph of the input. This is the first FPT algorithm for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. To further strengthen the relevance of this result, we show that the C-Planarity Testing problem retains its computational complexity when parameterized by several other graph-width parameters, which may potentially lead to faster algorithms.
Cite as

Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.IPEC.2019.9,
  author =	{Da Lozzo, Giordano and Eppstein, David and Goodrich, Michael T. and Gupta, Siddharth},
  title =	{{C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.9},
  URN =		{urn:nbn:de:0030-drops-114705},
  doi =		{10.4230/LIPIcs.IPEC.2019.9},
  annote =	{Keywords: Clustered planarity, carving-width, non-crossing partitions, FPT}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.19
Computing k-Modal Embeddings of Planar Digraphs

Authors: Juan José Besa, Giordano Da Lozzo, and Michael T. Goodrich

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Given a planar digraph G and a positive even integer k, an embedding of G in the plane is k-modal, if every vertex of G is incident to at most k pairs of consecutive edges with opposite orientations, i.e., the incoming and the outgoing edges at each vertex are grouped by the embedding into at most k sets of consecutive edges with the same orientation. In this paper, we study the k-Modality problem, which asks for the existence of a k-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks. First, since the 2-Modality problem can be easily solved in linear time, we consider the general k-Modality problem for any value of k>2 and show that the problem is NP-complete for planar digraphs of maximum degree Delta <= k+3. We relate its computational complexity to that of two notions of planarity for flat clustered networks: Planar Intersection-Link and Planar NodeTrix representations. This allows us to answer in the strongest possible way an open question by Di Giacomo [https://doi.org/10.1007/978-3-319-73915-1_37], concerning the complexity of constructing planar NodeTrix representations of flat clustered networks with small clusters, and to address a research question by Angelini et al. [https://doi.org/10.7155/jgaa.00437], concerning intersection-link representations based on geometric objects that determine complex arrangements. On the positive side, we provide a simple FPT algorithm for partial 2-trees of arbitrary degree, whose running time is exponential in k and linear in the input size. Second, motivated by the recently-introduced planar L-drawings of planar digraphs [https://doi.org/10.1007/978-3-319-73915-1_36], which require the computation of a 4-modal embedding, we focus our attention on k=4. On the algorithmic side, we show a complexity dichotomy for the 4-Modality problem with respect to Delta, by providing a linear-time algorithm for planar digraphs with Delta <= 6. This algorithmic result is based on decomposing the input digraph into its blocks via BC-trees and each of these blocks into its triconnected components via SPQR-trees. In particular, we are able to show that the constraints imposed on the embedding by the rigid triconnected components can be tackled by means of a small set of reduction rules and discover that the algorithmic core of the problem lies in special instances of NAESAT, which we prove to be always NAE-satisfiable - a result of independent interest that improves on Porschen et al. [https://doi.org/10.1007/978-3-540-24605-3_14]. Finally, on the combinatorial side, we consider outerplanar digraphs and show that any such a digraph always admits a k-modal embedding with k=4 and that this value of k is best possible for the digraphs in this family.
Cite as

Juan José Besa, Giordano Da Lozzo, and Michael T. Goodrich. Computing k-Modal Embeddings of Planar Digraphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.ESA.2019.19,
  author =	{Besa, Juan Jos\'{e} and Da Lozzo, Giordano and Goodrich, Michael T.},
  title =	{{Computing k-Modal Embeddings of Planar Digraphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.19},
  URN =		{urn:nbn:de:0030-drops-111404},
  doi =		{10.4230/LIPIcs.ESA.2019.19},
  annote =	{Keywords: Modal Embeddings, Planarity, Directed Graphs, SPQR trees, NAESAT}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.10
Morphing Contact Representations of Graphs

Authors: Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, and Vincenzo Roselli

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

Abstract
We consider the problem of morphing between contact representations of a plane graph. In a contact representation of a plane graph, vertices are realized by internally disjoint elements from a family of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in the graph. In a morph between two contact representations we insist that at each time step (continuously throughout the morph) we have a contact representation of the same type. We focus on the case when the geometric objects are triangles that are the lower-right half of axis-parallel rectangles. Such RT-representations exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We study piecewise linear morphs, where each step is a linear morph moving the endpoints of each triangle at constant speed along straight-line trajectories. We provide a polynomial-time algorithm that decides whether there is a piecewise linear morph between two RT-representations of a plane triangulation, and, if so, computes a morph with a quadratic number of linear morphs. As a direct consequence, we obtain that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the "top-most" triangle in both representations corresponds to the same vertex. This shows that the realization space of such RT-representations of any 4-connected plane triangulation forms a connected set.
Cite as

Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, and Vincenzo Roselli. Morphing Contact Representations of Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.SoCG.2019.10,
  author =	{Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano and Roselli, Vincenzo},
  title =	{{Morphing Contact Representations of Graphs}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{10:1--10:16},
  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.10},
  URN =		{urn:nbn:de:0030-drops-104145},
  doi =		{10.4230/LIPIcs.SoCG.2019.10},
  annote =	{Keywords: Contact representations, Triangulations, Planar morphs, Schnyder woods}
}
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.41
Approximation Algorithms for Facial Cycles in Planar Embeddings

Authors: Giordano Da Lozzo and Ignaz Rutter

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

Abstract
Consider the following combinatorial problem: Given a planar graph G and a set of simple cycles C in G, find a planar embedding E of G such that the number of cycles in C that bound a face in E is maximized. This problem, called Max Facial C-Cycles, was first studied by Mutzel and Weiskircher [IPCO '99, http://dx.doi.org/10.1007/3-540-48777-8_27) and then proved NP-hard by Woeginger [Oper. Res. Lett., 2002, http://dx.doi.org/10.1016/S0167-6377(02)00119-0]. We establish a tight border of tractability for Max Facial C-Cycles in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that strengthening any of these conditions makes the problem polynomial-time solvable. Our main results are approximation algorithms for Max Facial C-Cycles. Namely, we give a 2-approximation for series-parallel graphs and a (4+epsilon)-approximation for biconnected planar graphs. Remarkably, this provides one of the first approximation algorithms for constrained embedding problems.
Cite as

Giordano Da Lozzo and Ignaz Rutter. Approximation Algorithms for Facial Cycles in Planar Embeddings. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2018.41,
  author =	{Da Lozzo, Giordano and Rutter, Ignaz},
  title =	{{Approximation Algorithms for Facial Cycles in Planar Embeddings}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{41:1--41: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.41},
  URN =		{urn:nbn:de:0030-drops-99895},
  doi =		{10.4230/LIPIcs.ISAAC.2018.41},
  annote =	{Keywords: Planar Embeddings, Facial Cycles, Complexity, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.24
Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs

Authors: Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
A square-contact representation of a planar graph G = (V,E) maps vertices in V to interior-disjoint axis-aligned squares in the plane and edges in E to adjacencies between the sides of the corresponding squares. In this paper, we study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points. We characterize the partial 2-trees and the triconnected cycle-trees allowing for such representations. For partial 2-trees our characterization uses a simple forbidden subgraph whose structure forces a separating triangle in any embedding. For the triconnected cycle-trees, a subclass of the triconnected simply-nested graphs, we use a new structural decomposition for the graphs in this family, which may be of independent interest. Finally, we study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index.
Cite as

Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson. Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2017.24,
  author =	{Da Lozzo, Giordano and Devanny, William E. and Eppstein, David and Johnson, Timothy},
  title =	{{Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.24},
  URN =		{urn:nbn:de:0030-drops-82675},
  doi =		{10.4230/LIPIcs.ISAAC.2017.24},
  annote =	{Keywords: Square-Contact Representations, Partial 2-Trees, Simply-Nested Graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.33
On Planar Greedy Drawings of 3-Connected Planar Graphs

Authors: Giordano Da Lozzo, Anthony D'Angelo, and Fabrizio Frati

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
A graph drawing is greedy if, for every ordered pair of vertices (x,y), there is a path from x to y such that the Euclidean distance to y decreases monotonically at every vertex of the path. Greedy drawings support a simple geometric routing scheme, in which any node that has to send a packet to a destination "greedily" forwards the packet to any neighbor that is closer to the destination than itself, according to the Euclidean distance in the drawing. In a greedy drawing such a neighbor always exists and hence this routing scheme is guaranteed to succeed. In 2004 Papadimitriou and Ratajczak stated two conjectures related to greedy drawings. The greedy embedding conjecture states that every 3-connected planar graph admits a greedy drawing. The convex greedy embedding conjecture asserts that every 3-connected planar graph admits a planar greedy drawing in which the faces are delimited by convex polygons. In 2008 the greedy embedding conjecture was settled in the positive by Leighton and Moitra. In this paper we prove that every 3-connected planar graph admits a planar greedy drawing. Apart from being a strengthening of Leighton and Moitra's result, this theorem constitutes a natural intermediate step towards a proof of the convex greedy embedding conjecture.
Cite as

Giordano Da Lozzo, Anthony D'Angelo, and Fabrizio Frati. On Planar Greedy Drawings of 3-Connected Planar Graphs. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.SoCG.2017.33,
  author =	{Da Lozzo, Giordano and D'Angelo, Anthony and Frati, Fabrizio},
  title =	{{On Planar Greedy Drawings of 3-Connected Planar Graphs}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.33},
  URN =		{urn:nbn:de:0030-drops-72095},
  doi =		{10.4230/LIPIcs.SoCG.2017.33},
  annote =	{Keywords: Greedy drawings, 3-connectivity, planar graphs, convex drawings}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.13
Clustered Planarity with Pipes

Authors: Patrizio Angelini and Giordano Da Lozzo

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm.
Cite as

Patrizio Angelini and Giordano Da Lozzo. Clustered Planarity with Pipes. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.ISAAC.2016.13,
  author =	{Angelini, Patrizio and Da Lozzo, Giordano},
  title =	{{Clustered Planarity with Pipes}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.13},
  URN =		{urn:nbn:de:0030-drops-67817},
  doi =		{10.4230/LIPIcs.ISAAC.2016.13},
  annote =	{Keywords: Clustered Planarity, FPT, SEFE, Graph Drawing}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.126
Optimal Morphs of Convex Drawings

Authors: Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, and Vincenzo Roselli

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The linear bound is asymptotically optimal in the worst case.
Cite as

Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, and Vincenzo Roselli. Optimal Morphs of Convex Drawings. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 126-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.SOCG.2015.126,
  author =	{Angelini, Patrizio and Da Lozzo, Giordano and Frati, Fabrizio and Lubiw, Anna and Patrignani, Maurizio and Roselli, Vincenzo},
  title =	{{Optimal Morphs of Convex Drawings}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{126--140},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.126},
  URN =		{urn:nbn:de:0030-drops-51333},
  doi =		{10.4230/LIPIcs.SOCG.2015.126},
  annote =	{Keywords: Convex Drawings, Planar Graphs, Morphing, Geometric Representations}
}
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