We study the problem of drawing a dynamic graph, where each vertex appears in the graph at a certain time and remains in the graph for a fixed amount of time, called the window size. This defines a graph story, i.e., a sequence of subgraphs, each induced by the vertices that are in the graph at the same time. The drawing of a graph story is a sequence of drawings of such subgraphs. To support readability, we require that each drawing is straight-line and planar and that each vertex maintains its placement in all the drawings. Ideally, the area of the drawing of each subgraph should be a function of the window size, rather than a function of the size of the entire graph, which could be too large. We show that the graph stories of paths and trees can be drawn on a 2W × 2W and on an (8W + 1) × (8W + 1) grid, respectively, where W is the window size. These results are constructive and yield linear-time algorithms. Further, we show that there exist graph stories of planar graphs whose subgraphs cannot be drawn within an area that is only a function of W .

Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M. (2020). Graph Stories in Small Area. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 24(3), 269-292 [10.7155/jgaa.00530].

Graph Stories in Small Area

Borrazzo, Manuel;Da Lozzo, Giordano;Di Battista, Giuseppe;Frati, Fabrizio;Patrignani, Maurizio
2020-01-01

Abstract

We study the problem of drawing a dynamic graph, where each vertex appears in the graph at a certain time and remains in the graph for a fixed amount of time, called the window size. This defines a graph story, i.e., a sequence of subgraphs, each induced by the vertices that are in the graph at the same time. The drawing of a graph story is a sequence of drawings of such subgraphs. To support readability, we require that each drawing is straight-line and planar and that each vertex maintains its placement in all the drawings. Ideally, the area of the drawing of each subgraph should be a function of the window size, rather than a function of the size of the entire graph, which could be too large. We show that the graph stories of paths and trees can be drawn on a 2W × 2W and on an (8W + 1) × (8W + 1) grid, respectively, where W is the window size. These results are constructive and yield linear-time algorithms. Further, we show that there exist graph stories of planar graphs whose subgraphs cannot be drawn within an area that is only a function of W .
2020
Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M. (2020). Graph Stories in Small Area. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 24(3), 269-292 [10.7155/jgaa.00530].
File in questo prodotto:
File Dimensione Formato  
Published.pdf

accesso aperto

Descrizione: Published version at https://doi.org/10.7155/jgaa.00530
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 979.46 kB
Formato Adobe PDF
979.46 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/365949
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact