Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Castermans, T., van Garderen, M., Meulemans, W., Nöllenburg, M., & Yuan, X. (2019). Short Plane Supports for Spatial Hypergraphs. Journal of Graph Algorithms and Applications, 23(3), 463–498. https://doi.org/10.7155/jgaa.00499
E192-01 - Forschungsbereich Algorithms and Complexity
-
Journal:
Journal of Graph Algorithms and Applications
-
Date (published):
2019
-
Number of Pages:
36
-
Publisher:
Brown University
-
Peer reviewed:
Yes
-
Keywords:
Computer Science Applications; Theoretical Computer Science; General Computer Science; Computational Theory and Mathematics; Geometry and Topology
-
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 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 locati...
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.