Search Results

Documents authored by Patrignani, Maurizio

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.26
Rectilinear-Upward Planarity Testing of Digraphs

Authors: Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali, and Maurizio Patrignani

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
A rectilinear-upward planar drawing of a digraph G is a crossing-free drawing of G where each edge is either a horizontal or a vertical segment, and such that no directed edge points downward. Rectilinear-Upward Planarity Testing is the problem of deciding whether a digraph G admits a rectilinear-upward planar drawing. We show that: (i) Rectilinear-Upward Planarity Testing is NP-complete, even if G is biconnected; (ii) it can be solved in linear time when an upward planar embedding of G is fixed; (iii) the problem is polynomial-time solvable for biconnected digraphs of treewidth at most two, i.e., for digraphs whose underlying undirected graph is a series-parallel graph; (iv) for any biconnected digraph the problem is fixed-parameter tractable when parameterized by the number of sources and sinks in the digraph.
Cite as

Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali, and Maurizio Patrignani. Rectilinear-Upward Planarity Testing of Digraphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{didimo_et_al:LIPIcs.ISAAC.2023.26,
  author =	{Didimo, Walter and Kaufmann, Michael and Liotta, Giuseppe and Ortali, Giacomo and Patrignani, Maurizio},
  title =	{{Rectilinear-Upward Planarity Testing of Digraphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.26},
  URN =		{urn:nbn:de:0030-drops-193283},
  doi =		{10.4230/LIPIcs.ISAAC.2023.26},
  annote =	{Keywords: Graph drawing, orthogonal drawings, upward drawings, rectilinear planarity, upward planarity}
}
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.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}
}
Document
DOI: 10.4230/DagSemProc.08191.5
08191 Working Group Report – X-graphs of Y-graphs and their Representations

Authors: Vladimir Batagelj, Franz J. Brandenburg, Walter Didimo, Guiseppe Liotta, and Maurizio Patrignani

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract
We address graph decomposition problems that help the hybrid visualization of large graphs, where different graphic metaphors (node-link, matrix, etc.) are used in the same picture. We generalize the $X$-graphs of $Y$-graphs model introduced by Brandenburg (Brandenburg, F.J.: Graph clustering I: Cycles of cliques. In Di Battista, G., ed.: Graph Drawing (Proc. GD '97). Volume 1353 of Lecture Notes Comput. Sci., Springer-Verlag (1997) 158--168) to formalize the problem of automatically identifying dense subgraphs ($Y$-graphs, clusters) that are prone to be collapsed and shown with a matricial representation when needed. We show that (planar, $K_5$)-recognition, that is, the problem of identifying $K_5$ subgraphs such that the graph obtained by collapsing them is planar, is NP-hard. On the positive side, we show that it is possible to determine the highest value of $k$ such that $G$ is a (planar,$k$-core)-graph in $O(m + n log(n))$ time.
Cite as

Vladimir Batagelj, Franz J. Brandenburg, Walter Didimo, Guiseppe Liotta, and Maurizio Patrignani. 08191 Working Group Report – X-graphs of Y-graphs and their Representations. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{batagelj_et_al:DagSemProc.08191.5,
  author =	{Batagelj, Vladimir and Brandenburg, Franz J. and Didimo, Walter and Liotta, Guiseppe and Patrignani, Maurizio},
  title =	{{08191 Working Group Report – X-graphs of Y-graphs and their Representations}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.5},
  URN =		{urn:nbn:de:0030-drops-15563},
  doi =		{10.4230/DagSemProc.08191.5},
  annote =	{Keywords: Graph drawing, X-graphs of Y-graphs, visualization of large graphs}
}
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