Short plane supports for spatial hypergraphs. (English) Zbl 1419.05157

Summary: 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 drawings, also known as set visualizations. In this paper we consider visualizing spatial hypergraphs, where each vertex has a fixed 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 finding 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 first 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 effect of requiring planarity and acyclicity on the resulting support length. Furthermore, we evaluate the performance and trade-offs between solution quality and speed of heuristics relative to each other and compared to optimal solutions.


05C65 Hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)


Full Text: DOI


[1] H. A. Akitaya, M. L¨offler, and C. D. T´oth. Multi-colored spanning graphs. In Graph Drawing and Network Visualization (GD’16), volume 9801 of LNCS, pages 81-93. Springer, 2016. · Zbl 1478.68207
[2] B. Alper, N. Henry Riche, G. Ramos, and M. Czerwinski. Design study of LineSets, a novel set visualization technique. IEEE Transactions on Visualization and Computer Graphics, 17(12):2259-2267, 2011.
[3] B. Alsallakh, L. Micallef, W. Aigner, H. Hauser, S. Miksch, and P. Rodgers. The state of the art of set visualization.Computer Graphics Forum, 35(1):234-260, 2016.
[4] S. Bereg, K. Fleszar, P. Kindermann, S. Pupyrev, J. Spoerhase, and A. Wolff. Colored non-crossing Euclidean Steiner forest. In Algorithms and Computation (ISAAC’15), volume 9472 of LNCS, pages 429-441. Springer, 2015. · Zbl 1472.68109
[5] S. Bereg, M. Jiang, B. Yang, and B. Zhu. On the red/blue spanning tree problem. Theoretical Computer Science, 412(23):2459-2467, 2011. · Zbl 1216.68116
[6] U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry. Path-based supports for hypergraphs. Journal of Discrete Algorithms, 14:248-261, 2012. · Zbl 1247.05235
[7] K. Buchin, M. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek. On planar supports for hypergraphs. Journal of Graph Algorithms and Applications, 15(4):533-549, 2011. · Zbl 1276.05081
[8] T. Castermans, M. van Garderen, W. Meulemans, M. N¨ollenburg, and X. Yuan. Short plane supports for spatial hypergraphs. In Graph Drawing and Network Visualization (GD’18), volume 11282 of LNCS, pages 1-14. Springer, 2018. · Zbl 07023815
[9] C. Collins, G. Penn, and S. Carpendale.Bubble Sets: Revealing set relations with isocontours over existing visualizations.IEEE Transactions on Visualization and Computer Graphics, 15(6):1009-1016, 2009.
[10] G. Cumming. Understanding the new statistics: Effect sizes, confidence intervals, and meta-analysis. Routledge, 2013.
[11] K. Dinkla, M. El-Kebir, C.-I. Bucur, M. Siderius, M. J. Smit, M. A. Westenberg, and G. W. Klau. eXamine: Exploring annotated modules in networks. BMC Bioinformatics, 15:201, 2014.
[12] K. Dinkla, M. van Kreveld, B. Speckmann, and M. Westenberg.Kelp Diagrams: Point set membership visualization. Computer Graphics Forum, 31(3pt1):875-884, 2012.
[13] A. Efrat, Y. Hu, S. G. Kobourov, and S. Pupyrev. MapSets: Visualizing embedded and clustered graphs. Journal of Graph Algorithms and Applications, 19(2):571-593, 2015. · Zbl 1328.05124
[14] F. Hurtado, M. Korman, M. van Kreveld, M. L¨offler, V. Sacrist´an, A. Shioura, R. I. Silveira, B. Speckmann, and T. Tokuyama. Colored spanning graphs for set visualization. Computational Geometry: Theory and Applications, 68:262-276, 2018. · Zbl 1380.05065
[15] D. S. Johnson and H. O. Pollak. Hypergraph planarity and the complexity of drawing Venn diagrams. Journal of Graph Theory, 11(3):309-325, 1987. · Zbl 0654.05055
[16] P. Kindermann, B. Klemz, I. Rutter, P. Schnider, and A. Schulz. The partition spanning forest problem. Computing Research Repository (arXiv.org), 1809.02710, 2018. URL:
[17] B. Klemz, T. Mchedlidze, and M. N¨ollenburg. Minimum tree supports for hypergraphs and low-concurrency Euler diagrams. In Algorithm Theory (SWAT’14), volume 8503 of LNCS, pages 253-264. Springer, 2014. · Zbl 1416.68138
[18] E. Korach and M. Stern. The clustering matroid and the optimal clustering tree. Mathematical Programming, 98(1-3):385-414, 2003. · Zbl 1160.90638
[19] D. Lichtenstein. Planar formulae and their uses. SIAM Journal on Computing, 11(2):329-343, 1982. · Zbl 0478.68043
[20] W. Meulemans. Efficient optimal overlap removal: Algorithms and experiments. Computer Graphics Forum, 38(3):713-723, 2019.
[21] W. Meulemans, N. Henry Riche, B. Speckmann, B. Alper, and T. Dwyer. KelpFusion: A hybrid set visualization technique. IEEE Transactions on Visualization and Computer Graphics, 19(11):1846-1858, 2013.
[22] H. Purchase. Metrics for graph drawing aesthetics. Journal of Visual Languages and Computing, 13(5):501-516, 2002.
[23] P. J. Rodgers, G. Stapleton, B. Alsallakh, L. Micallef, R. Baker, and S. J. Thompson. A task-based evaluation of combined set and network visualization. Information Sciences, 367-368:58-79, 2016.
[24] E. Tufte. The Visual Display of Quantitative Information. Graphics Press, 2001.
[25] A. van Goethem, I. Kostitsyna, M. van Kreveld, W. Meulemans, M. Sondag, and J. Wulms. The painter’s problem: covering a grid with colored connected polygons. In Graph Drawing and Network Visualization (GD’17), volume 10692 of LNCS. Springer, 2018. · Zbl 07027010
[26] M. Wertheimer. Untersuchungen zur Lehre von der Gestalt. Psychologische Forschung, 4(1):301-350, 1923.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.