Graph (graph theory) in the context of Graph of a polytope

In polytope theory, the edge graph (also known as vertex-edge graph or just graph) of a polytope is a combinatorial graph whose vertices and edges correspond directly to the vertices and edges of the polytope.As a purely combinatorial object, the edge graph encodes incidence information, capturing which vertices are connected by edges, but it does not retain geometric data such as vertex positions or edge lengths. Further common names for the edge graph are skeleton and 1-skeleton, though some authors reserve these terms for the geometric embedding formed by the vertices and edges in the polytope's ambient space.There is no universally agreed upon notation for the edge graph of a polytope ${\displaystyle P}$. Common notations include ${\displaystyle G_{P}}$, ${\displaystyle G(P)}$ or ${\displaystyle \operatorname {skel} (P)}$.

Not all graphs are realizable as edge graphs of polytopes; those that are realizable in this manner are called polytopal graphs.Edge graphs of 3-dimensional polytopes are also called polyhedral graphs. The problem of deciding whether a given graph is polytopal or not is known as the realization problem and is NP hard in general dimension. In dimension three the problem is also called the Steinitz problem in recognition of its resolution by Ernst Steinitz.