Geodesic
Computing Hive Plots: A Combinatorial Framework
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023 , Tome 28 (2024) no. 2, pp. 101-129.

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

Hive plots are a graph visualization style placing vertices on a set of radial axes emanating from a common center and drawing edges as smooth curves connecting their respective endpoints. In previous work on hive plots, assignment to an axis and vertex positions on each axis were determined based on selected vertex attributes and the order of axes was prespecified. Here, we present a new framework focusing on combinatorial aspects of these drawings to extend the original hive plot idea and optimize visual properties such as the total edge length and the number of edge crossings in the resulting hive plots. Our framework comprises three steps: (1) partition the vertices into multiple groups, each corresponding to an axis of the hive plot; (2) optimize the cyclic axis order to bring more strongly connected groups near each other; (3) optimize the vertex ordering on each axis to minimize edge crossings. Each of the three steps is related to a well-studied, but NP-complete computational problem. We combine and adapt suitable exact and heuristic algorithmic approaches, implement them as an instantiation of our framework, and show in a case study how it can be applied in a practical setting. Furthermore, we conduct computational experiments to gain further insights regarding the algorithmic choices of our framework. The code of the implementation and a prototype web application can be found on OSF.
DOI : 10.7155/jgaa.v28i2.2990
Keywords: hive plots, graph drawing, combinatorial optimization

Martin Nöllenburg 1 ; Markus Wallinger 1

1 TU Wien 
@article{JGAA_2024_28_2_a5,
     author = {Martin N\"ollenburg and Markus Wallinger},
     title = {Computing {Hive} {Plots:} {A} {Combinatorial} {Framework}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {101--129},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2024},
     doi = {10.7155/jgaa.v28i2.2990},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2990/}
}
TY  - JOUR
AU  - Martin Nöllenburg
AU  - Markus Wallinger
TI  - Computing Hive Plots: A Combinatorial Framework
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 101
EP  - 129
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2990/
DO  - 10.7155/jgaa.v28i2.2990
LA  - en
ID  - JGAA_2024_28_2_a5
ER  - 
%0 Journal Article
%A Martin Nöllenburg
%A Markus Wallinger
%T Computing Hive Plots: A Combinatorial Framework
%J Journal of Graph Algorithms and Applications
%D 2024
%P 101-129
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2990/
%R 10.7155/jgaa.v28i2.2990
%G en
%F JGAA_2024_28_2_a5
Martin Nöllenburg; Markus Wallinger. Computing Hive Plots: A Combinatorial Framework. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023
					, Tome 28 (2024) no. 2, pp. 101-129. doi : 10.7155/jgaa.v28i2.2990. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2990/

Cité par Sources :