Planar Stories of Graph Drawings: Algorithms and Experiments
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916914654085120 |
|---|---|
| author | Binucci, Carla Cornelsen, Sabine Didimo, Walter Hong, Seok-Hee Katsanou, Eleni Patrignani, Maurizio Symvonis, Antonios Wolf, Samuel |
| author_facet | Binucci, Carla Cornelsen, Sabine Didimo, Walter Hong, Seok-Hee Katsanou, Eleni Patrignani, Maurizio Symvonis, Antonios Wolf, Samuel |
| contents | We address the problem of computing a dynamic visualization of a geometric graph $G$ as a sequence of frames. Each frame shows only a portion of the graph but their union covers $G$ entirely. The two main requirements of our dynamic visualization are: $(i)$ guaranteeing drawing stability, so to preserve the user's mental map; $(ii)$ keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of $G$. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_17532 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Planar Stories of Graph Drawings: Algorithms and Experiments Binucci, Carla Cornelsen, Sabine Didimo, Walter Hong, Seok-Hee Katsanou, Eleni Patrignani, Maurizio Symvonis, Antonios Wolf, Samuel Computational Geometry We address the problem of computing a dynamic visualization of a geometric graph $G$ as a sequence of frames. Each frame shows only a portion of the graph but their union covers $G$ entirely. The two main requirements of our dynamic visualization are: $(i)$ guaranteeing drawing stability, so to preserve the user's mental map; $(ii)$ keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of $G$. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph. |
| title | Planar Stories of Graph Drawings: Algorithms and Experiments |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2508.17532 |