<p>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:</p>

<p><a href="http://www.cs.uiuc.edu/~jeffe/pubs/crum.html">http://www.cs.uiuc.edu/~jeffe/pubs/crum.html</a></p>

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

<p><a href="http://sarielhp.org/p/09/set_cover_hard/">http://sarielhp.org/p/09/set_cover_hard/</a></p>

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

CC BY-SA 3.0
2014-03-24T03:07:36.737Z
2014-03-24T03:07:36.737Z
Sariel Har-Peled
<p>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.</p>

CC BY-SA 3.0
2014-03-24T14:50:36.883Z
2014-03-24T14:50:36.883Z
NisaiVloot
<p>Very important property : tree-width duality.</p>

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

<p>The abstract is as follow:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p><a href="http://www.labri.fr/perso/mazoit/uploads/Surface_duality_journal.pdf" rel="nofollow">http://www.labri.fr/perso/mazoit/uploads/Surface_duality_journal.pdf</a></p>

CC BY-SA 3.0
2014-03-24T14:37:39.347Z
As a side remark, the proof of this duality property was first claimed by D. Lapoire in his PhD thesis (under the direction of B. Courcelle). The proof used hypermap rewriting techniques if I'm correct.
Super8
CC BY-SA 3.0
2014-03-24T16:30:27.083Z
@Super8, That's interesting, do you have a reference to that phd thesis (sure I could search about it, but if you provide more information is more convenient).
Saeed
CC BY-SA 3.0
2014-03-25T11:22:57.480Z
@Super8, I searched about it, but this is from abstract of his thesis: "As a first consequence, we prove a conjecture of Robertson and Seymour: the dual of some planar graph $G$ has a tree-width at most equal to the treewidth of $G$". That means he just proved this for planar graph (also he didn't provide exact bound), but Mazoit work is for hyper graphs embedded on a fixed sourface and tight bound. Also the latter published in journal with referee, but the other one didn't.
Saeed
CC BY-SA 3.0
2014-03-24T09:52:47.427Z
2014-03-24T10:46:42.397Z
2014-03-24T10:46:42.397Z
Saeed
<p>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 <a href="http://arxiv.org/abs/0807.0336">this paper</a> by Matousek, Tancer and Wagner.</p>

<blockquote>
  <p>Does Fáry's Theorem hold in higher dimension?</p>
</blockquote>

<p>The answer is no. </p>

<p>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</p>

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

<p>and several examples have followed using results from matroid theory.</p>

<p>About the difference between PL and topological embeddings, this results from the general counter-examples arising from the <a href="http://en.wikipedia.org/wiki/Hauptvermutung">Hauptvermutung</a>: In dimensions 5 and more, there exist topological spheres which do not admit any piecewise-linear structure</p>

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

<p>You might want to take a look at the <a href="http://en.wikipedia.org/wiki/Euler_characteristic">Euler characteristic</a> (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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-03-24T13:19:20.733Z
2014-03-24T13:37:53.180Z
2014-03-24T13:37:53.180Z
Arnaud
<p>A <a href="http://en.wikipedia.org/wiki/Planar_graph" rel="noreferrer">planar graph</a> is a graph which can be embedded in the plane, without having crossing edges.</p>

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

<p>There has been <a href="http://research.microsoft.com/en-us/um/people/denzho/papers/hyper.pdf" rel="noreferrer">some work done</a> 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:</p>

<p>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.</p>

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

<p>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). </p>

<p><img src="https://i.sstatic.net/G6I2S.png" alt="example embedding"></p>

<p>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.</p>

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

<p>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.</p>

<p>An example of a property that could be useful comes from <a href="http://en.wikipedia.org/wiki/F%C3%A1ry%27s_theorem" rel="noreferrer">Fáry's Theorem</a> which suggests every planar graph can be embedded in a way that all of its edges are straight line segments. </p>

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

<p><strong>Are there any other properties that can be generalized?</strong> for example, can <a href="http://en.wikipedia.org/wiki/Planar_graph#Euler.27s_formula" rel="noreferrer">Euler's Formula</a> for planar graphs be generalized somehow to higher dimension? (although at the moment I'm not sure what would be the meaning of it).</p>

<graph-theory><planar-graphs><hypergraphs><embeddings><generalizations>
Which properties of planar graphs generalize to higher dimension / hypergraphs?
R B
# Which properties of planar graphs generalize to higher dimension / hypergraphs?

(Asked by: username_0 on 2014-03-23)

A [planar graph](http://en.wikipedia.org/wiki/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](http://research.microsoft.com/en-us/um/people/denzho/papers/hyper.pdf) 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).

![example embedding](https://i.sstatic.net/G6I2S.png)

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](http://en.wikipedia.org/wiki/F%C3%A1ry%27s_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](http://en.wikipedia.org/wiki/Planar_graph#Euler.27s_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).

**Tags:** graph-theory, planar-graphs, hypergraphs, embeddings, generalizations


---

## 4 answers

### Answer by username_5 on 2014-03-24. Score: 8 | Accepted answer

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](http://arxiv.org/abs/0807.0336) 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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 by username_1 on 2014-03-24. Score: 8

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 by username_2 on 2014-03-24. Score: 5

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 by username_3 on 2014-03-24. Score: 3

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>

> **Comments:**
> **username_4**: As a side remark, the proof of this duality property was first claimed by D. Lapoire in his PhD thesis (under the direction of B. Courcelle). The proof used hypermap rewriting techniques if I'm correct.  
> **username_3**: @username_4, That's interesting, do you have a reference to that phd thesis (sure I could search about it, but if you provide more information is more convenient).  
> **username_3**: @username_4, I searched about it, but this is from abstract of his thesis: "As a first consequence, we prove a conjecture of Robertson and Seymour: the dual of some planar graph $G$ has a tree-width at most equal to the treewidth of $G$". That means he just proved this for planar graph (also he didn't provide exact bound), but Mazoit work is for hyper graphs embedded on a fixed sourface and tight bound. Also the latter published in journal with referee, but the other one didn't.  

---

