Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
hagman
Posts:
1,923
Registered:
1/29/05
|
|
Re: Graph theory/topology query
Posted:
Aug 16, 2012 4:26 PM
|
|
Am Donnerstag, 16. August 2012 16:22:08 UTC+2 schrieb Bill Taylor:
> I am looking at planar graphs that might have distinct,
>
> i.e. non-homotopic, embeddings into the sphere.
>
>
>
> It is easy to construct counter-examples with
>
> 2 distinct embeddings, but they seem to be
>
> very simply connected. Are there any connectivity
>
> or other conditions known that guarantee
>
> mono-embeddability?
One such condition (probably there are less extreme ones):
If a graph G is maximal planar (if G' is G plus an
arbitrary edge then G' is not planar), then G
is "mono-embeddable".
Proof:
Obviously G is connected (adding an edge between two
components would not destroy planarity).
Consider two embeddings G1, G2 of G.
all faces are triangular (as otherwise one can add a diagonal
of a non-triagonal face without destroying planarity).
Consider a face a b c of G1.
Assume wlog that the sequence a,b,c is counterclockwise.
Enumerate the neighbours of a counterclockwise, starting with the one following c and ending one before b (which is a neighbour of b).
Continue by enumerating the neighbours of b ending one before c.
Continue by enumerating the neughbours of c ending before a.
This produces a cycle C in G1.
Let d,e be two vertices not among a,b,c.
For any oath from d to e that passes through a,b,c that path must enter and leave the "interior" of C. The part(s) of the path running in the interior
can be replaced with parts of C, thus shoing that there is a path
d to e that avoids a,b,c.
Assume a,b,c is not a face of G2.
Then there is a vertex d in the "interior" and a vertex e in the
"exterior" of the cycle abc. As shown with embedding G1,
there must exist a path from d to e that avoids a,b,c.
But that contradicts the fact that the path must cross the cycle abc (Jordan curve theorem).
Therefore G1 and G2 have the same faces, i.e. are equivalent.
By Euler, a planar graph with e = 3v-6 has only triangular faces
and hence is maximal planar.
hagman
|
|
|
|
