Simultaneous Embeddability of Two Partitions

Athenstädt, Jan Christoph and Hartmann, Tanja and Nöllenburg, Martin (2014) Simultaneous Embeddability of Two Partitions. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 64-75 (Official URL:

Full text not available from this repository.


We study the simultaneous embeddability of a pair of partitions of the same underlying set into disjoint blocks. Each element of the set is mapped to a point in the plane and each block of either of the two partitions is mapped to a region that contains exactly those points that belong to the elements in the block and that is bounded by a simple closed curve. We establish three main classes of simultaneous embeddability (weak, strong, and full embeddability) that differ by increasingly strict well-formedness conditions on how different block regions are allowed to intersect. We show that these simultaneous embeddability classes are closely related to different planarity concepts of hypergraphs. For each embeddability class we give a full characterization. We show that (i) every pair of partitions has a weak simultaneous embedding, (ii) it is NP-complete to decide the existence of a strong simultaneous embedding, and (iii) the existence of a full simultaneous embedding can be tested in linear time.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_6
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
P Styles > P.180 Cluster
P Styles > P.420 Hyper
Z Theory > Z.500 Representations
ID Code:1422

Repository Staff Only: item control page


Athenstädt, J.C., Hartmann, T., Nöllenburg, M.: Simultaneous embeddability of two partitions. CoRR, abs/1408.6019 (August 2014)

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, ch. 11, pp. 349–381. CRC Press (2013)

Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Blocks of hypergraphs applied to hypergraphs and outerplanarity. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 201–211. Springer, Heidelberg (2011)

Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Path-based supports for hypergraphs. J. Discrete Algorithms 14, 248–261 (2012)

Buchin, K., van Kreveld, M., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 345–356. Springer, Heidelberg (2010), see also Tech. Rep. UU-CS-2009-035, Utrecht University (2009)

Buja, A., Swayne, D.F., Littman, M.L., Dean, N., Hofmann, H., Chen, L.: Data visualization with multidimensional scaling. J. Comput. Graphical Statistics 17(2), 444–472 (2008)

Chaplick, S., Jelínek, V., Kratochvíl, J., Vyskočil, T.: Bend-bounded path intersection graphs: Sausages, noodles, and waffles on a grill. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 274–285. Springer, Heidelberg (2012)

Chow, S.: Generating and Drawing Area-Proportional Euler and Venn Diagrams. PhD thesis, University of Victoria (2007)

Collins, C., Penn, G., Carpendale, S.: Bubble sets: Revealing set relations with isocontours over existing visualizations. IEEE TVCG 15(6), 1009–1016 (2009)

de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 216–225. Springer, Heidelberg (2010)

Feng, Q.-W., Cohen, R., Eades, P.: Planarity for clustered graphs. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol. 979, pp. 213–226. Springer, Heidelberg (1995)

Flower, J., Fish, A., Howse, J.: Euler diagram generation. J. Visual Languages and Computing 19(6), 675–694 (2008)

Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974)

Johnson, D.S., Pollak, H.O.: Hypergraph planarity and the complexity of drawing Venn diagrams. J. Graph Theory 11(3), 309–325 (1987)

Kaufmann, M., van Kreveld, M., Speckmann, B.: Subdivision drawings of hypergraphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 396–407. Springer, Heidelberg (2009)

Kohonen, T.: Self-Organizing Maps, 3rd edn. Springer (2001)

Mäkinen, E.: How to draw a hypergraph. Int. J. Computer Math. 34(3-4), 177–185 (1990)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17(4), 717–728 (2001)

Simonetto, P., Auber, D., Archambault, D.: Fully automatic visualisation of overlapping sets. Computer Graphics Forum 28(3), 967–974 (2009)

S. Wagner and D. Wagner. Comparing Clusterings – An Overview. Tech. Rep. 2006-04, Department of Informatics, Universität Karlsruhe, 2007.

Walsh, T.R.: Hypermaps Versus Bipartite Maps. J. Combinatorial Theory Series B 18(2), 155–163 (1975)

Zykov, A.A.: Hypergraphs. Russian Mathematical Surveys 29(6), 89–156 (1974)