Search Results

Documents authored by Piselli, Tommaso

Document
DOI: 10.4230/LIPIcs.GD.2024.15
Bundling-Aware Graph Drawing

Authors: Daniel Archambault, Giuseppe Liotta, Martin Nöllenburg, Tommaso Piselli, Alessandra Tappini, and Markus Wallinger

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

Abstract
Edge bundling algorithms significantly improve the visualization of dense graphs by reducing the clutter of many edges visible on screen by bundling them together. As such, bundling is often viewed as a post-processing step applied to a drawing, and the vast majority of edge bundling algorithms consider a graph and its drawing as input. Another way of thinking about edge bundling is to simultaneously optimize both the drawing and the bundling. In this paper, we investigate methods to simultaneously optimize a graph drawing and its bundling. We describe an algorithmic framework which consists of three main steps, namely Filter, Draw, and Bundle. We then propose two alternative implementations and experimentally compare them against the state-of-the-art approach and the simple idea of drawing and subsequently bundling the graph. The experiments confirm that bundled drawings created by our framework outperform previous approaches according to standard quality metrics for edge bundling.
Cite as

Daniel Archambault, Giuseppe Liotta, Martin Nöllenburg, Tommaso Piselli, Alessandra Tappini, and Markus Wallinger. Bundling-Aware Graph Drawing. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{archambault_et_al:LIPIcs.GD.2024.15,
  author =	{Archambault, Daniel and Liotta, Giuseppe and N\"{o}llenburg, Martin and Piselli, Tommaso and Tappini, Alessandra and Wallinger, Markus},
  title =	{{Bundling-Aware Graph Drawing}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-212995},
  doi =		{10.4230/LIPIcs.GD.2024.15},
  annote =	{Keywords: Edge Bundling, Experimental Comparison, Graph Sparsification}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.49
Introducing Fairness in Graph Visualization (Poster Abstract)

Authors: Seok-Hee Hong, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, and Tommaso Piselli

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

Abstract
Information visualization tools are an essential component of many data-driven decision-making systems that rely on human feedback. The aim of this paper is to propose a novel research direction focused on fair visualizations of graphs.
Cite as

Seok-Hee Hong, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, and Tommaso Piselli. Introducing Fairness in Graph Visualization (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hong_et_al:LIPIcs.GD.2024.49,
  author =	{Hong, Seok-Hee and Liotta, Giuseppe and Montecchiani, Fabrizio and N\"{o}llenburg, Martin and Piselli, Tommaso},
  title =	{{Introducing Fairness in Graph Visualization}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{49:1--49:3},
  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.49},
  URN =		{urn:nbn:de:0030-drops-213338},
  doi =		{10.4230/LIPIcs.GD.2024.49},
  annote =	{Keywords: Network visualization, Fairness, Stress minimization}
}
Document
DOI: 10.4230/LIPIcs.SAND.2024.11
Partial Temporal Vertex Cover with Bounded Activity Intervals

Authors: Riccardo Dondi, Fabrizio Montecchiani, Giacomo Ortali, Tommaso Piselli, and Alessandra Tappini

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
Different variants of Vertex Cover have recently garnered attention in the context of temporal graphs. One of these variants is motivated by the need to summarize timeline activities in social networks. Here, the activities of individual vertices, representing users, are characterized by time intervals. In this paper, we explore a scenario where the temporal span of each vertex’s activity interval is bounded by an integer 𝓁, and the objective is to maximize the number of (temporal) edges that are covered. We establish the APX-hardness of this problem and the NP-hardness of the corresponding decision problem, even under the restricted condition where the temporal domain comprises only two timestamps and each edge appears at most once. Subsequently, we delve into the parameterized complexity of the problem, offering two fixed-parameter algorithms parameterized by: (i) the number k of temporal edges covered by the solution, and (ii) the number h of temporal edges not covered by the solution. Finally, we present a polynomial-time approximation algorithm achieving a factor of 3/4.
Cite as

Riccardo Dondi, Fabrizio Montecchiani, Giacomo Ortali, Tommaso Piselli, and Alessandra Tappini. Partial Temporal Vertex Cover with Bounded Activity Intervals. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dondi_et_al:LIPIcs.SAND.2024.11,
  author =	{Dondi, Riccardo and Montecchiani, Fabrizio and Ortali, Giacomo and Piselli, Tommaso and Tappini, Alessandra},
  title =	{{Partial Temporal Vertex Cover with Bounded Activity Intervals}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.11},
  URN =		{urn:nbn:de:0030-drops-198892},
  doi =		{10.4230/LIPIcs.SAND.2024.11},
  annote =	{Keywords: Temporal Graphs, Temporal Vertex Cover, Parameterized Complexity, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.18
On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges

Authors: Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, and Tommaso Piselli

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applications. In particular, an st-orientation orients each edge of the input graph such that the resulting digraph is acyclic, and it contains a single source s and a single sink t. Computing an st-orientation of a graph can be done efficiently, and it finds notable applications in graph algorithms and in particular in graph drawing. On the other hand, finding an st-orientation with at most k transitive edges is more challenging and it was recently proven to be NP-hard already when k = 0. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.
Cite as

Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, and Tommaso Piselli. On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.MFCS.2023.18,
  author =	{Binucci, Carla and Liotta, Giuseppe and Montecchiani, Fabrizio and Ortali, Giacomo and Piselli, Tommaso},
  title =	{{On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.18},
  URN =		{urn:nbn:de:0030-drops-185524},
  doi =		{10.4230/LIPIcs.MFCS.2023.18},
  annote =	{Keywords: st-orientations, parameterized complexity, graph drawing}
}
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