2 fixed latex

Here is another generalization of planar graphs.

Start with a d-dimensional polytope P with n vertices. For every 2-dimensional face F triangulate F by non crossing diagonals. So if F has k sides you add (k-3) edges. It is known that the total number of edges you get (including the original edges of the polytope) is at least $dn - {{d+1} \choose {2}$. 2}}$. A polytope is called "elementary" if equality holds. We can consider the following classes of graphs: 1) E_d = Graphs of elementary d-polytopes and all their subgraphs 2) F_d = Graphs obtained by elementary d-polytopes by triangulating all 2 faces by non crossing diagonals, and all their subgraphs. For d=3 both classes are the class of planar graphs. Some properties of planar graphs are known or conjectured to extend. 1) (robustness; conjectured) We can start instead of polytopes by arbitrary polyhedral (d-1)-dimensional pseudomanifolds. But it is conjectured that we will get precisely the same class of graphs. 2) (duality; known) If P is elementary so is its dual P* 3) (coloring; conjectured) Graphs in E_d (and perhaps even in F_d) are (d+1)-colorable. 1 Here is another generalization of planar graphs. Start with a d-dimensional polytope P with n vertices. For every 2-dimensional face F triangulate F by non crossing diagonals. So if F has k sides you add (k-3) edges. It is known that the total number of edges you get (including the original edges of the polytope) is at least$dn - {{d+1} \choose {2}\$. A polytope is called "elementary" if equality holds.

We can consider the following classes of graphs:

1) E_d = Graphs of elementary d-polytopes and all their subgraphs

2) F_d = Graphs obtained by elementary d-polytopes by triangulating all 2 faces by non crossing diagonals, and all their subgraphs.

For d=3 both classes are the class of planar graphs.

Some properties of planar graphs are known or conjectured to extend.

1) (robustness; conjectured) We can start instead of polytopes by arbitrary polyhedral (d-1)-dimensional pseudomanifolds. But it is conjectured that we will get precisely the same class of graphs.

2) (duality; known) If P is elementary so is its dual P*

3) (coloring; conjectured) Graphs in E_d (and perhaps even in F_d) are (d+1)-colorable.