Geodesic
Small Point-Sets Supporting Graph Stories
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirtieth International Symposium on Graph Drawing and Network Visualization, GD 2022 , Tome 27 (2023) no. 8, pp. 651-677.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In a graph story the vertices enter a graph one at a time and each vertex persists in the graph for a fixed amount of time $\omega$, called viewing window. At any time, the user can see only the drawing of the graph induced by the vertices in the viewing window and this determines a sequence of drawings. For readability, we require that all the drawings of the sequence are planar. For preserving the user's mental map we require that when a vertex or an edge is drawn, it has the same drawing for its entire life. We study the problem of computing the whole sequence of drawings by mapping the vertices only to $\omega+k$ given points, where $k$ is as small as possible. We show that: $(i)$ The problem does not depend on the specific set of points but only on the size of the point set; $(ii)$ the problem is NP-hard (even when $k$ is a given constant) and it is FPT when parameterized by $\omega+k$; $(iii)$ for $k=0$ there are families of graph stories that can be drawn independent of $\omega$, but also families that cannot be drawn even when $\omega$ is small; $(iv)$ there are families of graph stories that cannot be drawn for any fixed $k$ and families of graph stories that can be realized only when $k$ is larger than a certain threshold.
DOI : 10.7155/jgaa.00639
Keywords: dynamic graphs, planar graphs, time and graph drawing 
@article{JGAA_2023_27_8_a2,
     author = {Giuseppe Di Battista and Walter Didimo and Luca Grilli and Fabrizio Grosso and Giacomo Ortali and Maurizio Patrignani and Alessandra Tappini},
     title = {Small {Point-Sets} {Supporting} {Graph} {Stories}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {651--677},
     publisher = {mathdoc},
     volume = {27},
     number = {8},
     year = {2023},
     doi = {10.7155/jgaa.00639},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00639/}
}
TY  - JOUR
AU  - Giuseppe Di Battista
AU  - Walter Didimo
AU  - Luca Grilli
AU  - Fabrizio Grosso
AU  - Giacomo Ortali
AU  - Maurizio Patrignani
AU  - Alessandra Tappini
TI  - Small Point-Sets Supporting Graph Stories
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 651
EP  - 677
VL  - 27
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00639/
DO  - 10.7155/jgaa.00639
LA  - en
ID  - JGAA_2023_27_8_a2
ER  - 
%0 Journal Article
%A Giuseppe Di Battista
%A Walter Didimo
%A Luca Grilli
%A Fabrizio Grosso
%A Giacomo Ortali
%A Maurizio Patrignani
%A Alessandra Tappini
%T Small Point-Sets Supporting Graph Stories
%J Journal of Graph Algorithms and Applications
%D 2023
%P 651-677
%V 27
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00639/
%R 10.7155/jgaa.00639
%G en
%F JGAA_2023_27_8_a2
Giuseppe Di Battista; Walter Didimo; Luca Grilli; Fabrizio Grosso; Giacomo Ortali; Maurizio Patrignani; Alessandra Tappini. Small Point-Sets Supporting Graph Stories. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirtieth International Symposium on Graph Drawing and Network Visualization, GD 2022
					, Tome 27 (2023) no. 8, pp. 651-677. doi : 10.7155/jgaa.00639. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00639/

Cité par Sources :