Which properties of planar graphs generalize to higher dimension / hypergraphs?

Question

A planar graph is a graph which can be embedded in the plane, without having crossing edges.

Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k.

There has been some work done on embedding hypergraphs in the plane (with the context of clustering or some other application), but often, the data just can't be embedded in the plane. The solution could be either to force it, with some loss, or embed it in higher dimension as I suggest here:

A natural extension of planarity (IMO, at least) is a "$k$-simple-embedding" (is there a known different name for it?) of $G$: an embedding $\mathcal{M}:X\to \mathbb{R}^k$, such that there exist surfaces which connect all of the vertices of each hyperedge, and these do not intersect except for the endpoints.

(Think of the analogue in 2D, where each surface is an edge you can draw however you like).

Here's an example of a valid 3-simple-embedding of a 3-uniform-hypergraph. (Each vertex is colored by the hyperedges it is contained in, and each face represents an hyperedge).

Another example of 3-simple graph is the complete 3-uniform-hypergraph on 5 vertices $G=(V,V\times V\times V)$. To see this simply take 4 points in $\mathbb{R}^3$ which don't lie on a 2D plane, create a triangular pyramid (their convex hull), and place the fifth point in the center of the pyramid, connecting it to the other vertices.

Similarly, it seems that the complete 3-uniform-hypergraph on 6 vertices doesn't have a 3-simple-embedding.

There are some very useful properties of planar graphs which allow improved algorithms for hard problems when the graph is planar. Unfortunately, the data is often not planar, although sometimes it is of low dimensionality. I think that understanding which properties of planar graphs generalize will help us figure out which algorithms can be adapted for higher dimension with the same tool.

An example of a property that could be useful comes from Fáry's Theorem which suggests every planar graph can be embedded in a way that all of its edges are straight line segments.

Does Fáry's Theorem hold in higher dimension?, i.e. if a graph has a $k$-simple-embedding, does it have an embedding in which all of the hyper edges are hyperplanes?

Are there any other properties that can be generalized? for example, can Euler's Formula for planar graphs be generalized somehow to higher dimension? (although at the moment I'm not sure what would be the meaning of it).

Answer 1

As a first remark, your focus seems to be on hypergraphs but I think that most of the literature about embedding hypergraphs prefers to work with simplicial complexes. A good reference on these questions is this paper by Matousek, Tancer and Wagner.

Does Fáry's Theorem hold in higher dimension?

The answer is no.

There are actually 3 different notions of embeddability: with straight, piecewise-linear and continuous (hyper)-edges. In the plane, they all coincide, but in general they do not. Regarding straight-line embeddings, a first counter-example is due to Brehm

Brehm, U. (1983). A nonpolyhedral triangulated Möbius strip. Proc. Amer. Math. Soc., 89(3), 519–522. doi:10.2307/2045508

and several examples have followed using results from matroid theory.

About the difference between PL and topological embeddings, this results from the general counter-examples arising from the Hauptvermutung: In dimensions 5 and more, there exist topological spheres which do not admit any piecewise-linear structure

Are there any other properties that can be generalized? for example, can Euler's Formula for planar graphs be generalized somehow to higher dimension?

You might want to take a look at the Euler characteristic (jump to the topological definition), which relates the alternating sum of the number of $k$-dimensional simplices with the alternating sum of the betti numbers of your complex.

Similarly, it seems that the complete 3-hypergraph on 6 vertices doesn't have 3-simple-embedding.

Indeed, this results from the van Kampen-Flores obstruction. This is explained in remarkable detail and clarity in Matousek's book Using the Borsuk Ulam Theorem.

Answer 2

Oh oh. You want to be very very careful. Contact graphs of convex polytopes in 3d can realize any graph. Surprisingly, the clique can be realized by n polytopes that are n rotated and translated copies of the same polytope (the mind boggles). See this paper:

http://www.cs.uiuc.edu/~jeffe/pubs/crum.html

This already implies that you can encode pretty nasty graphs as intersection graphs of triangles in 3d. See section 4 of this paper:

http://sarielhp.org/p/09/set_cover_hard/

BTW, I am interested in a similar version of your problem by trying to understand how geometric intersection graph behaves...

Answer 3

Schnyder Theorem states that a graph is planar iff its incidence poset has dimension at most 3. This has been extended by Mendez to arbitrary simplicial complexes (see "Geometric Realization of Simplicial Complexes", Graph Drawing 1999: 323-332). Strangely enough there is a much older paper with a very similar title "The geometric realization of a semi-simplicial complex", but I suspect that it's on a different topic.

Answer 4

Very important property : tree-width duality.

e.g look at : Tree-width of hyper-graphs and surface duality by Frederic Mazoit,

The abstract is as follow:

In Graph Minors III, Robertson and Seymour write: "It seems that the tree- width of a planar graph and the tree-width of its geometric dual are approximately equal, indeed, we have convinced ourselves that they differ by at most one." They never gave a proof of this. In this paper, we prove a generalization of this statement to embedding of hypergraphs on general surfaces, and we prove that our bound is tight.

http://www.labri.fr/perso/mazoit/uploads/Surface_duality_journal.pdf