[Back]

T. Castermans, M. van Garderen, W. Meulemans, M. Nöllenburg, X. Yuan:
"Short Plane Supports for Spatial Hypergraphs";
Talk: International Symposium on Graph Drawing and Network Visualization (GD), Barcelona; 2018-09-26 - 2018-09-28; in: "Graph Drawing and Network Visualization (GD'2018)", T. Biedl, A. Kerren (ed.); Springer Lecture Notes in Computer Science, 11282 (2018), 53 - 66.

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 visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This is the case, e.g., when modeling set systems of geospatial locations as hypergraphs. By applying established aesthetic quality cri- teria we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set V . We first show, from a theoretical point of view, that the problem is NP-hard already under rather mild conditions as well as a negative approxima- bility results. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for com- puting short plane supports. We report results from computational ex- periments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Further, we evaluate the performance and trade-offs between solution quality and speed of several heuristics relative to each other and compared to optimal solutions.

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 visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed location in the plane. This is the case, e.g., when modeling set systems of geospatial locations as hypergraphs. By applying established aesthetic quality cri- teria we are interested in finding supports that yield plane straight-line drawings with minimum total edge length on the input point set V . We first show, from a theoretical point of view, that the problem is NP-hard already under rather mild conditions as well as a negative approxima- bility results. Therefore, the main focus of the paper lies on practical heuristic algorithms as well as an exact, ILP-based approach for com- puting short plane supports. We report results from computational ex- periments that investigate the effect of requiring planarity and acyclicity on the resulting support length. Further, we evaluate the performance and trade-offs between solution quality and speed of several heuristics relative to each other and compared to optimal solutions.

http://dx.doi.org/10.1007/978-3-030-04414-5_4

https://arxiv.org/pdf/1808.09729.pdf