![]() | This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see
Wikipedia:So you made a userspace draft. Find sources:
Google (
books ·
news ·
scholar ·
free images ·
WP refs) ·
FENS ·
JSTOR ·
TWL |
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 is known as -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.
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:
For -polytopes with no characterization of edge graphs is known or expected. Some general statements can be made:
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 , 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 this is usually harder to argue.
Some operations on polytopes translate to their edge graphs in a simple way.
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 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.
Simplices have a complete edge graph; but in dimension there are other polytopes whose edge graph is complete. These are known as 1-neighborly polytopes. For example, both the -dimension simplex and the 4-dimensional cyclic polytope have edge graph .
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. [3]
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 of two triangles is a 5-dimensional simplex, whereas the direct sum is the 4-dimensional cyclic polytope on six vertices which too has a complete edge graph.
Reconstruction of the combinatorial type is possible in special cases or when given access to additional data:
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.
The decision problem of whether a given graph G is polytopal is decidable and known to be NP hard. If G has maximum degree we can enumerate all compatible lattices up to rank ; 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.
![]() | This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see
Wikipedia:So you made a userspace draft. Find sources:
Google (
books ·
news ·
scholar ·
free images ·
WP refs) ·
FENS ·
JSTOR ·
TWL |
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 is known as -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.
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:
For -polytopes with no characterization of edge graphs is known or expected. Some general statements can be made:
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 , 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 this is usually harder to argue.
Some operations on polytopes translate to their edge graphs in a simple way.
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 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.
Simplices have a complete edge graph; but in dimension there are other polytopes whose edge graph is complete. These are known as 1-neighborly polytopes. For example, both the -dimension simplex and the 4-dimensional cyclic polytope have edge graph .
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. [3]
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 of two triangles is a 5-dimensional simplex, whereas the direct sum is the 4-dimensional cyclic polytope on six vertices which too has a complete edge graph.
Reconstruction of the combinatorial type is possible in special cases or when given access to additional data:
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.
The decision problem of whether a given graph G is polytopal is decidable and known to be NP hard. If G has maximum degree we can enumerate all compatible lattices up to rank ; 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.