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 Fry's Theorem which suggests every planar graph can be embedded in a way that all of its edges are straight line segments. Does Fry'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).
Which properties of planar graphs generalize to higher dimension / hypergraphs?
graph theory;planar graphs;hypergraphs;embeddings;generalizations
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 Fry'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 BrehmBrehm, U. (1983). A nonpolyhedral triangulated Mbius strip. Proc. Amer. Math. Soc., 89(3), 519522. doi:10.2307/2045508and 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 structureAre 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.