Short plane supports for spatial hypergraphs
| Autor: | Mereke van Garderen, Thom Castermans, Wouter Meulemans, Xiaoru Yuan, Martin Nöllenburg |
|---|---|
| Přispěvatelé: | Algorithms, Geometry and Applications, Applied Geometric Algorithms |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Vertex (graph theory) Discrete mathematics Hypergraph Geospatial analysis General Computer Science Computer science Vertex connectivity Point set 0102 computer and information sciences computer.software_genre 01 natural sciences Planarity testing Computer Science Applications Theoretical Computer Science Computational Theory and Mathematics 010201 computation theory & mathematics Computer Science - Computational Geometry Geometry and Topology ddc:004 Heuristics computer MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Graph Algorithms and Applications, 23(3), 463-498. Brown University |
| ISSN: | 1526-1719 |
| Popis: | 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 criteria 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 approximability results. 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. 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. Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|