Small Point-Sets Supporting Graph Stories
| Autor: | Di Battista, Giuseppe, Didimo, Walter, Grilli, Luca, Grosso, Fabrizio, Ortali, Giacomo, Patrignani, Maurizio, Tappini, Alessandra |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 drawing the entire sequence 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 its size; $(ii)$ the problem is NP-hard and is FPT when parameterized by $\omega+k$; $(iii)$ there are families of graph stories that can be drawn with $k=0$ for any $\omega$, while for $k=0$ and small values of $\omega$ 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$. Comment: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022) |
| Databáze: | arXiv |
| Externí odkaz: |
|