Talk:Graph of a polytope

Deciding polytopality of graphs

I was thinking to include a section on the algorithmic aspects of detecting edge graphs, but realized I just don't know enough. So I left it out for now or for someone more knowledgeable to step in. Here is what I had written so far:

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$ one 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. NP hardness, already for polytopes of dimension four, follows from the universality theorem of 4-polytopes due to Jürgen Richter-Gebert.

MWinter4 (talk) 15:06, 30 July 2025 (UTC)

Geometric skeleton

Some authors distinguish between edge graph as the purely combinatorial object, and skeleton (or 1-skeleton) as the embedding of the edge graph into the ambient space. Perhaps a section about this distinction could be included, which also discusses the geometric aspects of this embedding. Here are some ideas:

• 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.

MWinter4 (talk) 15:23, 30 July 2025 (UTC)

References

What title to use?

The main term used throughout the text is edge graph and ideally the title contains this term. But the term "edge graph" is also used for the Line graph in graph theory, which might be confusing. Currently the title is "Graph of a polytope".

The following alternatives come to mind:

• "Edge graph (polytope)", but paranthesis are generally to be avoided.
• "Edge graph of a polytope", but quite long and should get a hatnote to distinguish from Line graph.
• "Polytope edge graph", but this is an uncommon term and maybe unnecessarily long. The shorter title "Polytope graph" is closer to Polyhedral graph, but the intent is slightly different: polytope graphs (or polytopal graphs as they are called in the article) form a graph class; but edge graph is more like a property of a polytope that is a graph. The title "Graph of a polyope" expresses this "property nature" more explicitly.

MWinter4 (talk) 16:31, 30 July 2025 (UTC)