Say that a graph is "$d$-dimensional" if it is the node-disjoint union of $1$-skeletons of closed convex polytopes in $d$ dimensions, or a subgraph thereof. So the $2$-dimensional graphs are exactly those that are the disjoint union of cycles and paths, the $3$-dimensional graphs are exactly the planar graphs, and so on. (Is there a standard name for this?)

Clearly for any fixed $d$ the $d$-dimensional graphs are minor-closed, so by the graph minor theorem they can be characterized by finitely many forbidden minors. Is it known what the forbidden minor sets are for general $d$, or even for any $d > 3$? Alternately, is it known that the forbidden minor sets need to be unreasonably large (like how the torus needs $>1000$ forbidden minors)?

  • $\begingroup$ Shall the $3$-dimensional graphs be $3$-connected? $\endgroup$ – Bullet51 Apr 12 at 7:29
  • $\begingroup$ @Bullet51: No, since we are allowed to take subgraphs. $\endgroup$ – Ilya Bogdanov Apr 12 at 10:07
  • $\begingroup$ I'm wondering whether there's any obstruction at all: one can take the skeleton of the 3d cubic lattice and embed any graph in it. $\endgroup$ – Bullet51 Apr 12 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.