%0 Book Section %1 journals/jgaa/CastermansGMNY19 %A Castermans, Thom %A van Garderen, Mereke %A Meulemans, Wouter %A Nöllenburg, Martin %A Yuan, Xiaoru %D 2019 %E Biedl, T. %E Kerren, A. %I Springer International Publishing %J Graph Drawing and Network Visualization. GD 2018. Lecture Notes in Computer Science %K 2019 B02 from:leonkokkoliadis sfbtrr161 visus visus:garderme %P 53-66 %R 10.1007/978-3-030-04414-5_4 %T Short Plane Supports for Spatial Hypergraphs %U https://link.springer.com/chapter/10.1007/978-3-030-04414-5_4#citeas %V 11282 %X AgraphG=(V, E)isasupportof a hypergraphH=(V, S)if every hyperedge induces a connected subgraph inG. Supports are usedfor certain types of hypergraph visualizations. In this paper we considervisualizingspatialhypergraphs, where each vertex has a fixed location inthe plane. This is the case, e.g., when modeling set systems of geospatiallocations as hypergraphs. By applying established aesthetic quality cri-teria we are interested in finding supports that yield plane straight-linedrawings with minimum total edge length on the input point setV.Wefirst show, from a theoretical point of view, that the problem isNP-hardalready under rather mild conditions as well as a negative approxima-bility results. Therefore, the main focus of the paper lies on practicalheuristic algorithms as well as an exact, ILP-based approach for comput-ing short plane supports. We report results from computational exper-iments that investigate the effect of requiring planarity and acyclicityon the resulting support length. Further, we evaluate the performanceand trade-offs between solution quality and speed of several heuristicsrelative to each other and compared to optimal solutions.

@inbook{journals/jgaa/CastermansGMNY19, abstract = {AgraphG=(V, E)isasupportof a hypergraphH=(V, S)if every hyperedge induces a connected subgraph inG. Supports are usedfor certain types of hypergraph visualizations. In this paper we considervisualizingspatialhypergraphs, where each vertex has a fixed location inthe plane. This is the case, e.g., when modeling set systems of geospatiallocations as hypergraphs. By applying established aesthetic quality cri-teria we are interested in finding supports that yield plane straight-linedrawings with minimum total edge length on the input point setV.Wefirst show, from a theoretical point of view, that the problem isNP-hardalready under rather mild conditions as well as a negative approxima-bility results. Therefore, the main focus of the paper lies on practicalheuristic algorithms as well as an exact, ILP-based approach for comput-ing short plane supports. We report results from computational exper-iments that investigate the effect of requiring planarity and acyclicityon the resulting support length. Further, we evaluate the performanceand trade-offs between solution quality and speed of several heuristicsrelative to each other and compared to optimal solutions.}, added-at = {2020-10-09T12:31:48.000+0200}, author = {Castermans, Thom and van Garderen, Mereke and Meulemans, Wouter and Nöllenburg, Martin and Yuan, Xiaoru}, biburl = {https://puma.ub.uni-stuttgart.de/bibtex/290662e67b3c6064e2bf5537fcb9d65f8/mueller}, description = {Short Plane Supports for Spatial Hypergraphs}, doi = {10.1007/978-3-030-04414-5_4}, editor = {Biedl, T. and Kerren, A.}, ee = {https://doi.org/10.7155/jgaa.00499}, interhash = {ab37db2e94a0653d0494ed37c215f967}, intrahash = {90662e67b3c6064e2bf5537fcb9d65f8}, journal = { Graph Drawing and Network Visualization. GD 2018. Lecture Notes in Computer Science}, keywords = {2019 B02 from:leonkokkoliadis sfbtrr161 visus visus:garderme}, pages = {53-66}, publisher = {Springer International Publishing}, timestamp = {2020-10-09T10:31:48.000+0200}, title = {Short Plane Supports for Spatial Hypergraphs}, url = {https://link.springer.com/chapter/10.1007/978-3-030-04414-5_4#citeas}, volume = 11282, year = 2019 }