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, skeleton, 1-skeleton or just graph) of a polytope is a graph whose (combinatorial) vertices and edges correspond to the (geometric) vertices and edges of the polytope. The edge graph is a combinatorial object, retaining the incidence information between the vertices and edges of the polytope, but not their geometric information, such as the positions of the vertices or the lengths of the edges. Some authors use the term skeleton or 1-skeleton to refer to the geometric object formed by the vertices and edges of the polytope embedded in the ambient space.

Not all graphs are edge graphs of polytopes. Graphs which do arise in this way are called polytopal graphs. Edge graphs of 3-dimensional polytopes are also called polyhedral graphs. The Steinitz problem is the problem of deciding whether a given graph is polytopal or not. The Steinitz problem is NP hard for polytopes in general dimension.

Information about the polytope's faces of dimension two or higher is not immediately accessible from the edge graph, and can often not be reconstruction from it at all. To capture the full combinatorial structure of a polytope, including the number of faces of each dimension and the incidence relations between them, one needs to work with the polytope's face lattice. In analogy to the 1-skeleton, the part of the face lattice that captures the combinatorics of faces up to dimension $k$ is called the $k$-skeleton of the polytope.

This article focuses on edge graphs of convex polytopes.

Introduction

A convex polytope $P\subset {\mathbb {R}}^{n}$ is bounded by faces of different dimensions. Faces of dimension 0 are points and are called vertices of the polytope; faces of dimension 1 are line segments and are called edges of the polytope. These vertices and edges behave like the identically named elements of graphs, in particular,

• two edges are either disjoint or intersect in a vertex.
• each edge contains exactly two vertices.

It is therefore natural to reinterpret the polytope's vertices and edges as the combinatorial vertices and edges of a graph. This graph is the edge graph of $P$. Historically, the terms "vertex" and "edge" were actually used first in the context of polyhedra, and only later became standard terminology in graph theory.

There exists no established standard notation for the edge graph. Some common notations for the edge graph of a polytope $P$ are $G_{P}$, $G(P)$ or $\operatorname {skel} (P)$.

General properties

The edge graph of a convex polytope is a finite simple graph. It is connected, since 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 polytope's 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 still well-understood: by Steinitz's theorem the edge graphs of 3-polytopes are precisely 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. 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$ it is usually harder to decide this question.

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 is known as the halved cube graph and is the edge graphs of the corresponding demihypercube.
• 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. This includes the edge graphs of both simplices $H(1,q)$ and hypercubes $H(d,2)$, but also other polytopes such as the (3,3)-duoprism $H(2,3)$.
• 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 natural way.

• The edge graph of the Cartesian product $P\times Q$ of two polytopes 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 join $P\star Q$ of two polytopes is the graph join of the edge graphs of $P$ and $Q$. The graph join is constructed from the union of the edge graphs by adding all edges between them. The same edge graph is obtained for the direct sum $P\oplus Q$ (the dual of the Cartesian product) under the assumption that both $P$ and $Q$ are of dimension at least two.

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

Reconstruction from the edge graph

Given the edge graph of a polytope of dimension three or lower it is possible to reconstruct the polytope's full combinatorics, that is, the complete list of faces and incidences between them. For example, the 2-dimensional faces of a 3-polytope correspond exactly to the non-separating induced cycles in the edge graph. Also, for polytopes of dimension up to three it is possible to tell the dimension of the polytope from the edge graph. In dimension $d\geq 4$ neither of this is the case. There exist combinatorially distinct polytopes with isomorphic edge graphs, and even polytopes of different dimensions with isomorphic edge graphs.

Examples of non-reconstructability

The edge graph of a simplex is a complete graph. However, in dimension $d\geq 4$ there are other polytopes whose edge graph is complete. These are called 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 general technique for constructing combinatorially distinct polytopes with the same edge graph is by using the direct sum and the join of polytopes. While these operations never generate polytopes of the same dimension, the resulting polytopes always have the same edge graph (assuming that we start from polytopes of dimension at least two). For example, the join $\Delta \star \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)$. Both have $K_{6}$ as their edge graph.

Reconstruction in special cases

Reconstruction of the polytope's full combinatorics from the edge graph is possible in special cases or when additional data is available:

• The combinatorics of a simple polytope can be reconstructed from the edge graph. This was first proven by Blind & Mani. Later, a short proof was given by Gil Kalai using unique sink orientations.
• The combinatorics of a zonotope can be reconstructed from the edge graph.
• For simplicial polytopes, given the polytope's edge graph and its space of self-stresses it is possible to reconstruct the polytope up to affine equivalence.

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 properties not shared by general embeddings of the edge graph.

• the skeleton is thight. This means that every hyperplane cuts the embedding into at most two connected components. This is a consequence of Balinski's theorem.
• the skeleton is a Colin de Verdière embedding of the edge graph.
• for 3-polytopes the skeleton is a linkless and knotless embedding of the edge graph.

Other relations

• The simplex algorithm traverses the edge graph of a polytope to find the optimal solution to a linear program.
• The Hirsch conjecture asserts that the edge graph of a $d$-polytope has diameter at most $d$. A counterexample was found by Santos in 2012,. The conjecture has since been reformulated in different ways. As of July 2024, no polynomial bound on the diameter in $d$ is known.

Deciding polytopality of graphs

The problem of deciding whether a given graph $G$ is polytopal is decidable and known to be NP hard. Given $G$ of maximum degree $\Delta$ we can enumerate all compatible face lattices up to rank $\Delta +1$. Their realizability is decidable by the existential theory of the reals. Alternatively one can enumerate compatible oriented matroids and test their embeddability via the biquadratic final polynomial method. The hardness, already for polytopes of dimension four, follows from the universality theorem of 4-polytopes due to Jürgen Richter-Gebert.

External links

• www.example.com