Representation of Planar Hypergraphs by Contacts of Triangles

De Fraysseix, Hubert and Ossona de Mendez, Patrice and Rosenstiehl, Pierre (2008) Representation of Planar Hypergraphs by Contacts of Triangles. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 125-136 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_15).

Full text not available from this repository.

Abstract

Many representation theorems extend from planar graphs to planar hypergraphs. The authors proved in [10] that every planar graph has a representation by contact of triangles. We prove here that this representation result extend to planar linear hypergraphs. Although the graph proof was simple and led to a linear time drawing algorithm, the extension for hypergraphs needs more work. The proof we give here relies on a combinatorial characterization of those hypergraphs which are representable by contact of segments in the plane, We propose some possible generalization directions and open problems, related to the order dimension of the incidence posets of hypergraphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_15
Keywords:hypergraphs; planarity; contact representation
Classifications:Z Theory > Z.500 Representations
ID Code:810

Repository Staff Only: item control page

References

E.M. Andreev, On convex polyhedra in Lobacevskiı spaces, Matematicheskii Sbornik 81 (1970), 445–478.

C. Berge, Graphes et hypergraphes, second ed., Dunod, Paris, 1973.

G. Brightwell and W.T. Trotter, The order dimension of planar maps, SIAM journal on Discrete Mathematics 10 (1997), no. 4, 515–528.

R. Cori, Un code pour les graphes planaires et ses applications, vol. 27, Société Mathématique de France, Paris, 1975.

R. Cori and A. Machì, Maps, hypermaps and their automorphisms, Expo. Math. 10 (1992), 403–467.

B. Dushnik and E.W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600–610.

H. de Fraysseix and P. Ossona de Mendez, Intersection Graphs of Jordan Arcs, Contemporary Trends in Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, DIMATIA-DIMACS, 1999, Stirin 1997 Proc., pp. 11–28.

H. de Fraysseix and P. Ossona de Mendez, Barycentric systems and stretchability, Discrete Applied Mathematics 155 (2007), no. 9, 1079–1095.

H. de Fraysseix and P. Ossona de Mendez, On representations by contact and intersection of segments, Algorithmica 47 (2007), no. 4, 453–463.

H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl, On triangle contact graphs, Combinatorics, Probability and Computing 3 (1994), 233–246.

H. de Fraysseix, J. Pach, and R. Pollack, Small sets supporting Fary embeddings of planar graphs, Twentieth Annual ACM Symposium on Theory of Computing, 1988, pp. 426–433.

H. de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), 41–51.

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

R.P. Jones, Colourings of hypergraphs, Ph.D. thesis, Royal Holloway College, Egham, 1976, p. 209.

P. Koebe, Kontaktprobleme der konformen Abbildung, Ber. Verh. Schs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88 (1936), 141–164.

P. Ossona de Mendez, Orientations bipolaires, Ph.D. thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1994.

P. Ossona de Mendez, Geometric Realization of Simplicial Complexes, Graph Drawing (J. Kratochvil, ed.), Lecture Notes in Computer Science, vol. 1731, Springer, 1999, pp. 323–332.

P. Ossona de Mendez, Realization of posets, Journal of Graph Algorithms and Applications 6 (2002), no. 1, 149–153.

P. Rosenstiehl and R.E. Tarjan, Rectilinear planar layout and bipolar orientation of planar graphs, Discrete and Computational Geometry 1 (1986), 343–353.

E.R. Scheinerman, Intersection classes and multiple intersection parameters of graphs, Ph.D. thesis, Princeton University, 1984.

E.R. Scheinerman and D.B. West, The interval number of a planar graph: Three intervals suffice, Journal of Combinatorial Theory, Series B 35 (1983), 224–239.

W. Schnyder, Planar graphs and poset dimension, Order 5 (1989), 323–343.

W. Schnyder, Embedding planar graphs in the grid, First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138–147.

R. Tamassia and I.G. Tollis, Tessalation representation of planar graphs, Proc. Twenty-Seventh Annual Allerton Conference on Communication, Control, and Computing, 1989, pp. 48–57.

W.T. Trotter, Combinatorics and partially ordered sets: Dimension theory, John Hopkins series in the mathematical sciences, Johns Hopkins University Press, London, 1992.

T.R.S. Walsh, Hypermaps versus bipartite maps, J. Combinatorial Theory 18(B) (1975), 155–163.

A.T. White, Graphs, Groups and Surfaces, revised ed., Mathematics Studies, vol. 8, North-Holland, Amsterdam, 1984.

A.A. Zykov, Hypergraphs, Uspeki Mat. Nauk 6 (1974), 89–154.