Geodesic
Short Plane Supports for Spatial Hypergraphs
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-sixth International Symposium on Graph Drawing and Network Visualization, GD 2018 , Tome 23 (2019) no. 3, pp. 463-498.

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

A graph $G=(V,E)$ is a support of a hypergraph $H=(V,S)$ if every hyperedge induces a connected subgraph in $G$. Supports are used for certain types of hypergraph drawings, also known as set visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This scenario appears when, e.g., modeling set systems of geospatial locations as hypergraphs. Following established aesthetic quality criteria, we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set $V$. From a theoretical point of view, we first show that the problem is NP-hard already under rather mild conditions, and additionally provide a negative approximability result. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for computing short plane supports. We report results from computational experiments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Furthermore, we evaluate the performance and trade-offs between solution quality and speed of heuristics relative to each other and compared to optimal solutions.
DOI : 10.7155/jgaa.00499
Keywords: hypergraphs, support graphs, set visualization, length minimization, computational experiments 
@article{JGAA_2019_23_3_a1,
     author = {Thom Castermans and Mereke van Garderen and Wouter Meulemans and Martin N\"ollenburg and Xiaoru Yuan},
     title = {Short {Plane} {Supports} for {Spatial} {Hypergraphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {463--498},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2019},
     doi = {10.7155/jgaa.00499},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00499/}
}
TY  - JOUR
AU  - Thom Castermans
AU  - Mereke van Garderen
AU  - Wouter Meulemans
AU  - Martin Nöllenburg
AU  - Xiaoru Yuan
TI  - Short Plane Supports for Spatial Hypergraphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 463
EP  - 498
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00499/
DO  - 10.7155/jgaa.00499
LA  - en
ID  - JGAA_2019_23_3_a1
ER  - 
%0 Journal Article
%A Thom Castermans
%A Mereke van Garderen
%A Wouter Meulemans
%A Martin Nöllenburg
%A Xiaoru Yuan
%T Short Plane Supports for Spatial Hypergraphs
%J Journal of Graph Algorithms and Applications
%D 2019
%P 463-498
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00499/
%R 10.7155/jgaa.00499
%G en
%F JGAA_2019_23_3_a1
Thom Castermans; Mereke van Garderen; Wouter Meulemans; Martin Nöllenburg; Xiaoru Yuan. Short Plane Supports for Spatial Hypergraphs. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-sixth International Symposium on Graph Drawing and Network Visualization, GD 2018
					, Tome 23 (2019) no. 3, pp. 463-498. doi : 10.7155/jgaa.00499. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00499/

Cité par Sources :