2
$\begingroup$

Motivation

There are at least three interpretations of an abstract polyhedral (= planar 3-vertex-connected) graph:

  • the 1-skeleton of a convex polyhedron (when embedded into $\mathbb{R}^3$)

  • a polygonization of the sphere (when embedded into the sphere $\mathbb{S}^2$)

  • a polygonization of a polygon – for each of its faces (when embedded into the plane $\mathbb{R}^2$)

In any case there are many geometric realizations:

  • of a polyhedron

  • of a polygonization of the sphere

  • of a polygon and its polygonizations

Question

I'd like to understand in an abstract setting:

What do these interpretations and realizations have to do with each other?

Example

For many (but not all) polyhedral graphs there is a realization as a convex polyhedron that is inscribable into the sphere. A central projection of this polyhedron back onto the sphere induces a polygonization of the sphere.

Taken for granted is Steinitz' theorem. The question is not about this.

EDIT: For completeness' sake I should mention embeddings of a polyhedral graph into:

  • the hyperbolic space $\mathbb{H}^2$

  • the 3-dimensional sphere $\mathbb{S}^3$

  • the hyperbolic space $\mathbb{H}^3$

Improve this question
$\endgroup$
2
  • $\begingroup$ Dear Hans, what do you mean by a polygon and its polygonizations? $\endgroup$
    – Gil Kalai
    Commented Feb 2, 2013 at 23:07
  • $\begingroup$ Quite simple: every embedding of a planar graph into $\mathbb{R}^2$ has an outer face - "the polygon" - which is "polygonized" by the rest of the graph. $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 2, 2013 at 23:23

1 Answer 1

Reset to default
4
$\begingroup$

This is not a complete answer, just a pointer on one aspect of your question, the relationship between two of your three "interpretations." As you note, not all polyhedral graphs have a realization that is inscribable in a sphere. Here is an explicit example:

"Uninscribable 4-Regular Polyhedron." Electronic Geometry Model No. 2003.08.001. David Eppstein and Michael Dillencourt. (Link to abstract, and to the images below)


            alt text      alt text

There is a characterization of the inscribable polyhedral graphs, obtained in 1992:

Craig Hodgson, Igor Rivin, and Warren Smith. "A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere." (arXiv link)

Now that I understand better the thrust of the question from the OP's comment below, I believe this recent survey by Günter Rote should be helpful:

"Realizing Planar Graphs as Convex Polytopes." Graph Drawing. Lecture Notes in Computer Science Volume 7034, 2012, pp 238-241. (Springer link)

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Joseph Thank you for the representation of polyhedrons by differently colored (shaded) faces and vertices. This helps a lot. Can this be automated (given an abstract polyhedral graph)? $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 2, 2013 at 17:26
  • $\begingroup$ @Hans: I have used Tutte's embedding theorem: Every 3-connected planar graph can be straight-line embedded in the plane so that each face is convex and each vertex a wheel. I'll add a reference to my answer. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 2, 2013 at 18:31
  • $\begingroup$ For those who don't have a Springer account: page.mi.fu-berlin.de/rote/Papers/slides/… $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 2, 2013 at 23:39
  • $\begingroup$ @Joseph: Do you know of a comparable result for inscribable polyhedral graphs in flat space $\mathbb{R}^3$? (I am not so familiar with hyperbolic space and have a lack of imagination.) $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 3, 2013 at 14:37
  • $\begingroup$ @Joseph: BTW, the second reference (to Rote) is a late answer to another question of mine: mathoverflow.net/questions/119455/…. Thanks a lot for this one, too! $\endgroup$
    – Hans-Peter Stricker
    Commented Feb 3, 2013 at 14:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .