On Planar Supports for Hypergraphs

Buchin, Kevin and Van Kreveld, Marc and Meijer, Henk and Verbeek, Kevin (2010) On Planar Supports for Hypergraphs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 345-356 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_33).

Full text not available from this repository.

Abstract

A graph G is a support for a hypergraph H = (V, S) if the vertices of G correspond to the vertices of H such that for each hyperedge Si ∈ S the subgraph of G induced by Si is connected. G is a planar support if it is a support and planar. Johnson and Pollak [9] proved that it is NP-complete to decide if a given hypergraph has a planar support. In contrast, there are polynomial time algorithms to test whether a given hypergraph has a planar support that is a path, cycle, or tree. In this paper we present an algorithm which tests in polynomial time if a given hypergraph has a planar support that is a tree where the maximal degree of each vertex is bounded. Our algorithm is constructive and computes a support if it exists. Furthermore, we prove that it is already NP-hard to decide if a hypergraph has a 3-outerplanar support.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_33
Classifications:P Styles > P.420 Hyper
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:1073

Repository Staff Only: item control page

References

Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)

Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. Journal of the ACM 30, 479–513 (1983)

Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973)

Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and planarity using pq-tree algorithms. Journal of Computer and System Sciences 13, 335–379 (1976)

Brinkmeier, M., Werner, J., Recknagel, S.: Communities in graphs and hypergraphs. In: 16th ACM Conference on Information and Knowledge Management, pp. 869–872 (2007)

Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

Flower, J., Howse, J.: Generating Euler diagrams. In: Hegarty, M., Meyer, B., Narayanan, N.H. (eds.) Diagrams 2002. LNCS (LNAI), vol. 2317, pp. 61–75. Springer, Heidelberg (2002)

Hsu, W.L.: A simple test for the consecutive ones property. Journal of Algorithms 43(1), 1–16 (2002)

Johnson, D., Pollak, H.: Hypergraph planarity and the complexity of drawing Venn diagrams. Journal of 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)

Korach, E., Stern, M.: The clustering matroid and the optimal clustering tree. Mathematical Programming, Series B 98, 385–414 (2003)

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)

Sander, G.: Layout of directed hypergraphs with orthogonal hyperedges. In: Kreowski, H.-J., Montanari, U., Orejas, F., Rozenberg, G., Taentzer, G. (eds.) GD 2004. LNCS, vol. 3393, pp. 381–386. Springer, Heidelberg (2005)

Tamura, A., Tamura, Y.: Degree constrained tree embedding into points in the plane. Information Processing Letters 44, 211–214 (1992)

Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing 13, 566–579 (1984)

Tucker, A.: Matrix characterizations of circular-arc graphs. Pacific Journal of Mathematics 39(2), 535–545 (1971)