
arXiv: 2208.14126
handle: 11590/433089 , 11391/1542315 , 11391/1564741
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 $ω$, 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 drawing the entire sequence by mapping the vertices only to $ω+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 its size; $(ii)$ the problem is NP-hard and is FPT when parameterized by $ω+k$; $(iii)$ there are families of graph stories that can be drawn with $k=0$ for any $ω$, while for $k=0$ and small values of $ω$ there are families of graph stories that can be drawn and others that cannot; $(iv)$ there are families of graph stories that cannot be drawn for any fixed $k$ and families of graph stories that require at least a certain $k$.
Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)
FOS: Computer and information sciences, Dynamic graphs; Planar graphs; Time and graph drawing, families of graph stories, Graph representations (geometric and intersection representations, etc.), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Structural characterization of families of graphs, Dynamic Graphs, Planar Graphs, Time and Graph Drawing, viewing window
FOS: Computer and information sciences, Dynamic graphs; Planar graphs; Time and graph drawing, families of graph stories, Graph representations (geometric and intersection representations, etc.), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Structural characterization of families of graphs, Dynamic Graphs, Planar Graphs, Time and Graph Drawing, viewing window
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
