Short Plane Supports for Spatial Hypergraphs

Abstract

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.