Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
T. Castermans, M. van Garderen, W. Meulemans, M. Nöllenburg, X. Yuan:
"Short Plane Supports for Spatial Hypergraphs";
Vortrag: International Symposium on Graph Drawing and Network Visualization (GD),
Barcelona;
26.09.2018
- 28.09.2018; in: "Graph Drawing and Network Visualization (GD'2018)",
T. Biedl, A. Kerren (Hrg.);
Springer Lecture Notes in Computer Science,
11282
(2018),
S. 53
- 66.
Kurzfassung deutsch:
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.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-04414-5_4
Elektronische Version der Publikation:
https://arxiv.org/pdf/1808.09729.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.