User:MWinter4/Edge graph of a polytope

The edge graphs of the square, cube and tesseract.

In polytope theory the edge graph (also vertex-edge graph, 1-skeleton, skeleton or just graph) of a polytope is a graph whose vertices and edges correspond to the geometric vertices and edges of the polytope. The edge graph is one of the simplest combinatorial objects associated with a polytope. It captures the first three layers of the face lattice (with faces of dimension -1, 0 and 1). The analogous structure that captures faces up to dimension $k$ is known as $k$-skeleton. The edge graph is therefore also known as the 1-skeleton (or just skeleton) of the polytope.

The edge graph is a purely combinatorial graph and discards of all geometric information, such as positions of the vertices and lengths of edges. Some authors use the term 1-skeleton (or just skeleton) to refer to the geometric embedding of the edge graph, while others use this term synonymously with edge graph.

The edge graph also discards most of the combinatorial data, for example, information about 2- and higher-dimensional faces and their incidences. The object that retains the full combinatorial information about the polytope, while still discarding of all the geometry, is the face lattice.

Some authors do however emphasize a distinction between these terms: the edge graph refers to an abstract graph isomorphic to the vertex-edge incidence structure of the polytope, whereas the 1-skeleton refer to the geometric embedding of the edge graph in Euclidean space given by the polytope's geometry.

A graph is said to be polytopal if it is the edge-graph of some (usually convex) polytope. Edge graphs of 3-dimensional polytopes are also known as polyhedral graphs. Most graphs are not polytopal, and deciding whether a graph is polytopal is believed to be computationally hard. In general, edge graphs do not determine the polytope's combinatorial type or dimension.

This article focuses on edge graphs of convex polytopes.

General properties

The edge graph of a convex polytope is a finite simple graph. It is always connected and a path between any two vertices can be constructed using the simplex algorithm. For low-dimensional polytopes the structure of the edge graph is essentially determined by the dimension:

• the only 0-dimensional polytope is the point; its edge graph is $K_{1}$.
• the only 1-dimensional polytope is the line segment; its edge graph is $K_{2}$.
• the 2-dimensional polytopes are polygons. The edge graph of an $n$-sided polygon is $C_{n}$, the cycle with $n$ vertices.
• the edge graphs of 3-dimensional polytopes are rich in structure but are still well-understood: by Steinitz's theorem edge graphs of 3-polytopes are exactly the 3-vertex-connected planar graphs (also known as polyhedral graphs).

For $d$-polytopes with $d\geq 4$ no characterization of edge graphs is known or expected. Some general statements can be made:

• the edge graph has minimum degree at least $d$. If every vertex of a $d$-polytope has degree exactly $d$ (i.e. the edge graph is $d$-regular), then the polytope is said to be simple.
• the edge graph is $d$-vertex connected. This is known as Balinski's theorem.
• the edge graph contains a subidivision of the complete graph $K_{d+1}$. In particular, for $d\geq 4$, the edge graph contains a $K_{5}$-minor and is not planar.

It is in general non-trivial to determine whether a given graph is the edge graph of a polytope, that is, whether it is a polytopal graph. For some graph classes, such as graphs of minimum degree $\delta =3$, the above properties can help to decide this question. For example, the Petersen graph is 3-regular. Hence, if it were polytopal, it would be the edge graph of a 3-polytope. It is however not planar and thus cannot be the edge graph of a 3-polytope. For graphs of minimum degree $\delta \geq 4$ this is usually harder to argue.

Examples

Named families

• The cycle graph $C_{n}$ is the edge graph of the $n$-sided polygon.
• The complete graph $K_{n}$ is the edge graph of the $(n-1)$-dimensional simplex (including the triangle, tetrahedron and 5-cell).
• The hypercube graph $Q_{n}$ is th edge graph of the $n$-dimensional hypercube (including square and cube). Its distance-two graph, the halved cube graph, is the edge graphs of the corresponding demicube.
• The Turán graph $T(2n,n)$ (also known as "cocktail party graph" ) is the edge graph of the $n$-dimensional cross-polytope (including octahedron and 16-cell).
• The Johnson graph $J(n,k)$ is the edge graph of the hypersimplex $\Delta _{n,k}$.
• The Hamming graph $H(d,q)$ is the edge graph of the $d$-th cartesian power of the $(q-1)$-dimensional simplex.
• The Bruhat graph is the edge graph of the permutahedron. More generally, the Cayley graph of a finite Coxeter group (with the natural generators) is the edge graph of the corresponding omnitruncated uniform polytope, or more generally, the edge graph of a generic orbit polytope of the associated reflection group.

Other named examples

• The icosahedral graph is the edge graph of the regular icosahedron.
• The dodecahedral graph is the edge graph of the regular dodecahedron.
• The Schläfli graph is the edge graph of the 6-dimensional 2₂₁ polytope.
• The Gosset graph is the edge graph of the 7-dimensional 3₂₁ polytope.

Operations

Some operations on polytopes translate to their edge graphs in a simple way.

• The edge graph of the Cartesian product $P\times Q$ is the Cartesian graph product of the edge graphs of $P$ and $Q$. For example, the product of a cycle graph and $K_{1}$ is the edge graph of a prism.

• The edge graph of the free join $P\bowtie Q$ is obtained by taking the union of the edge graphs of $P$ and $Q$ and adding all edges with ends in different polytopes. The same holds for the direct sum $P\oplus Q$ if both $P$ and $Q$ have dimension at least two.

• The edge graph of the connected sum $P\,\#\,Q$ is obtained by gluing their edge graphs at the subgraph that corresponds to the facet at which $P$ and $Q$ are glued.

• For 3-dimensional polytopes the edge graph of the polar dual polytope is the dual graph of its edge graph.

Reconstruction from the edge graph

Given the edge graph of a polytope of dimension up to three it is possible to reconstruct the polytope's combinatorial type, that is, the complete list of faces and incidences between them. For example, the faces of a 3-polytope correspond exactly to the non-separating induced cycles in the edge graph. In particular, in low dimension it is possible to tell the dimension of the polytope from the graph.

In dimension $d\geq 4$ this is no longer the case. There exist combinatorially distinct polytopes with isomorphic edge graphs, and even polytopes of different dimensions with isomorphic edge graphs.

Examples of non-reconstruction

Simplices have a complete edge graph; but in dimension $d\geq 4$ there are other polytopes whose edge graph is complete. These are known as 1-neighborly polytopes. For example, both the $d$-dimension simplex and the 4-dimensional cyclic polytope $C_{4}(d+1)$ have edge graph $K_{d+1}$.

Hypercubes of sufficiently large dimension share their edge graphs with neighborly cubical polytopes. For example, the edge graph of the 10-dimensional hypercube is also the edge graph of a 4-dimensional polytope.

One way to construct combinatorially distinct polytopes with the same edge graph is using that the direct sum and the free join of two polytopes of dimension at least two result in polytopes with the same edge graph (see the section on operations). For example, the free join $\Delta \bowtie \Delta$ of two triangles is a 5-dimensional simplex, whereas the direct sum $\Delta \oplus \Delta$ is the 4-dimensional cyclic polytope on six vertices $C_{4}(6)$ which too has a complete edge graph.

Reconstruction in special cases

Reconstruction of the combinatorial type is possible in special cases or when given access to additional data:

• The combinatorics of a simple polytope can be reconstructed from the edge graph using unique sink orientations.
• The combinatorics of a zonotope can be reconstructed from the edge graph.
• Edge-transitive polytopes can be recostructed up to scale and orientation from the edge graph.
• For simplicial polytopes, given the edge graph and the space of self-stresses allows reconstruction up to affine equivalence.
• Centrally symmetric inscribed polytopes are uniquely determined by the edge graph and edge lengths up to isometry.

Geometric skeleton

While the term edge graph is almost unanimously understood to be a purely combinatorial object, the term skeleton (or 1-skeleton) is used by some authors to refer to a geometric realization of the edge graph. ...

The term skeleton or 1-skeleton, while often used interchangeably with edge graph, is used by some authors to refer to the specific embedding of the edge graph given by the polytope, that is, the edge graph plus the placement of the vertices in the ambient space.

The skeleton of a polytope has a number of special properties compared to a general embedding of the edge graph.

• it is thight. This means that every hyperplane cuts the embedding into at most two componenst.
• it is a Colin de Verdiere embedding of the edge graph.
• in dimension three, the skeleton is a linkless and knotless embedding of the edge graph.

Other relations

• The simplex algorithm traverses the edge graph of polytope to find the solution to a linear program.
• The Hirsch conjecture asserts that the edge graph of a $d$-polytope has diameter at most $d$. While this exact formulation is now known to be wrong due to a counterexample by Santos, no polynomial bounds on the diameter in $d$ have been proven.

Deciding polytopality of graphs

The decision problem of whether a given graph G is polytopal is decidable and known to be NP hard. If G has maximum degree $\Delta$ we can enumerate all compatible lattices up to rank $\Delta +1$; their realizability is decidable by the existencial theory of the reals. Alternatively one can enumerate compatible oriented matroids and test their embeddability via the biquadratic final polynomial method. The hardness follows from Richert-Gebert's universality theorem.

External links

• www.example.com