[Zurück]

T. Castermans, M. van Garderen, W. Meulemans, M. Nöllenburg, X. Yuan:
"Short Plane Supports for Spatial Hypergraphs";
Journal of Graph Algorithms and Applications, 23 (2019), 3; S. 463 - 498.

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 cer-
tain types of hypergraph drawings, also known as set visualizations. In
this paper we consider visualizing spatial hypergraphs, where each ver-
tex has a xed 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 nding 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 rst 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 e ect
of requiring planarity and acyclicity on the resulting support length. Fur-
thermore, we evaluate the performance and trade-o s between solution
quality and speed of heuristics relative to each other and compared to
optimal solutions.

http://dx.doi.org/10.7155/jgaa.00499

https://publik.tuwien.ac.at/files/publik_284605.pdf