Abstract
We introduce the concept of subdivision drawings of hypergraphs. In a subdivision drawing each vertex corresponds uniquely to a face of a planar subdivision and, for each hyperedge, the union of the faces corresponding to the vertices incident to that hyperedge is connected. Vertex-based Venn diagrams and concrete Euler diagrams are both subdivision drawings. In this paper we study two new types of subdivision drawings which are more general than concrete Euler diagrams and more restricted than vertex-based Venn diagrams. They allow us to draw more hypergraphs than the former while having better aesthetic properties than the latter.
This research was initiated during the Bertinoro Workshop on Graph Drawing, 2008. Bettina Speckmann is supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.022.707.
Chapter PDF
Similar content being viewed by others
References
Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973)
Bertault, F., Eades, P.: Drawing hypergraphs in the subset standard. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 164–169. Springer, Heidelberg (2001)
Brinkmeier, M., Werner, J., Recknagel, S.: Communities in graphs and hypergraphs. In: ACM CIKM 2007, pp. 869–872 (2007)
Didimo, W., Giordano, F., Liotta, G.: Overlapping cluster planarity. In: Asia-Pacific Symposium on Visualisation, pp. 73–80 (2007)
Dillencourt, M.B.: Realizability of Delaunay triangulations. Information Processing Letters 33(6), 283–287 (1990)
Eschbach, T., Günther, W., Becker, B.: Orthogonal hypergraph drawing for improved visibility. J. of Graph Algorithms and Applications 10(2), 141–157 (2006)
Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J. of the ACM 30(3), 514–550 (1983)
Flower, J., Howse, J.: Generating Euler diagrams. In: Hegarty, M., Meyer, B., Narayanan, N.H. (eds.) Diagrams 2002. LNCS, vol. 2317, pp. 61–75. Springer, Heidelberg (2002)
Johnson, D., Pollak, H.: Hypergraph planarity and the complexity of drawing Venn diagrams. J. of Graph Theory 11(3), 309–325 (1987)
Lundgren, J.R.: Food webs, competition graphs, competition-common enemy graphs and niche graphs. Applications of Combinatorics and Graph Theory to the Biological and Social Sciences 17, 221–243 (1989)
Mäkinen, E.: How to draw a hypergraph. International J. of Computer Mathematics 34, 177–185 (1990)
Ramadan, E., Tarafdar, A., Pothen, A.: A hypergraph model for the yeast protein complex network. In: 18th Parallel and Distributed Processing Symposium, pp. 189–190 (2004)
Ruskey, F., Weston, M.: A survey of Venn diagrams. The Electronic J. of Combinatorics (2005), http://www.combinatorics.org/Surveys/ds5/VennEJC.html
Sander, G.: Layout of directed hypergraphs with orthogonal hyperedges. In: Kreowski, H.-J., Montanari, U., Orejas, F., Rozenberg, G., Taentzer, G. (eds.) Formal Methods in Software and Systems Modeling. LNCS, vol. 3393, pp. 381–386. Springer, Heidelberg (2005)
Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)
Verroust, A., Viaud, M.L.: Ensuring the drawability of extended Euler diagrams for up to 8 sets. In: Blackwell, A.F., Marriott, K., Shimojima, A. (eds.) Diagrams 2004. LNCS, vol. 2980, pp. 128–141. Springer, Heidelberg (2004)
Walsh, T.: Hypermaps versus bipartite maps. J. of Combinatorial Theory 18, 155–163 (1975)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kaufmann, M., van Kreveld, M., Speckmann, B. (2009). Subdivision Drawings of Hypergraphs. In: Tollis, I.G., Patrignani, M. (eds) Graph Drawing. GD 2008. Lecture Notes in Computer Science, vol 5417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00219-9_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-00219-9_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00218-2
Online ISBN: 978-3-642-00219-9
eBook Packages: Computer ScienceComputer Science (R0)