Representations of Planar Graphs:

Theorem 8 of [1] (an conjecture of Tutte [2]) says:
Let G be a 3-connected planar graph, and G* its planar dual.
It is possible to draw G and G* simultaniously in the plane with
straight-line edges so that the edges of G cross the edges of G*
at right angles.

Question1:
----------
Is there an embedding in R^2 like the one of theorem 8 with the
following additional condition:
That the edges of G are bisected by the edges of its planar dual G*.

The origin of this question was the atempt to draw a
convex polyhedron and its dual in such a way that their edges 
cross at right angles. Then we get a wrapper-polyhedrom which has
all of the vertices of the original and the dual one. The faces of 
the wrapper-polyhedrom are quadrangles whose diagonals are
the edges of original and the dual one. If we start with a
cube we get a rombic-dodecahedron. Then we iterate the process.
Is the wrapping procedure well defined?

Question2:
----------
Is there an embedding in R^2 like the on of theorem 8 with the
following additional condition:
That the edges of G are bisected by the edges of G* or their extensions.

In other words:
Is it possible to place the vertices of a 3-connected planar graph G
in the plane R^2, such that the Delaunay-graph of the points is equal G?

Question3:
----------
Is each planar graph a subgraph of a Delaunay graph?
(Or can the the subgraphs of Delaunay graphs be characterized?)

There is a subdivision of every planar graph that is
a subgraph of a Delaunay graph.


Further properties of Delaunay graphs:
- Delaunay graphs are 1-tough, but not all are Hamiltonian. [3]

-----------------------------------------------------------------
[1] G. B. Brightwell, E. R. Scheinerman
   Representations of Planar Graphs
   SIAM J. Disc. Math. 6:2 (1993) 214-229

[2] W. Tutte
   How to draw a graph
   Proc. LMS, 13:3 (1963) 743-768
   
[3] M. B. Dillencourt
   A non-Hamiltonian, nondegenerate Delaunay triangulation,
   Inforamtion Process. Letters 25 (1987) 149-151
-----------------------------------------------------------------
     Subject: Re: points in general position
        Date: 2 Aug 97 01:07:15 GMT
        From: eppstein@euclid.ics.uci.edu
Organization: University of Illinois at Urbana-Champaign
  Newsgroups: comp.theory, sci.math.research

In <33E21D6E.6178@cs.duke.edu> Jeff Erickson <jeffe@cs.duke.edu> writes:
> Niall Graham wrote:
> > Q1. Has the number of Voronoi diagrams been determined?
> An n^{O(n)} upper bound follows from the techniques in my previous post ...

Actually, there are only 2^O(n) (unlabeled) planar graphs and therefore
2^O(n) combinatorially distinct unlabeled Voronoi diagrams in R^2.

> > Q2. Is every inner-triangulated graph a delaunay graph?
> No.  Every Delaunay graph is the 1-skeleton (the vertices and edges) of
> a convex polyhedron whose vertices lie on a sphere.  A polyhedron is
> called "inscribable" if it is combinatorially equivalent to a polyhedron
> with cospherical vertices.  In 1927, Steinitz showed that not all
> polyhedra are inscribable, even if all of the faces are triangles.

A DT is actually an inscribable graph minus one vertex ("at infinity").
See Dillencourt and Smith, ICALP 1993 for some related work -- they show
that (for non-general-position inputs with cocircular points) not every
way of filling out the Voronoi dual to a triangulation can be realized
as the DT of a general-position perturbation of the points.

That paper includes references to earlier work by Rivin and Smith (which
I'm not sure ever got formally published) describing how to test
inscribability in polynomial time.  A polyhedron is inscribable iff its
edges can be assigned weights satisfying certain linear inequalities and
equalities -- there are exponentially many inequalities but you can find
a violated inequality quickly, which is all that's needed to apply the
ellipsoid method for linear programming.
--
David Eppstein          UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu    http://www.ics.uci.edu/~eppstein/