From: delgado@olaf.de (Olaf Delgado) Subject: Re: Number of embeddings of planar graphs Date: 4 Feb 2000 04:00:05 -0600 Newsgroups: sci.math.research Summary: [missing] In article <3899A3C5.E94C233A@informatik.uni-freiburg.de>, Christoph Dornheim writes: > does anyone know how many topologically different embeddings a planar > graph can have (2^n or more)? Is there a least upper bound known in the > literature ? > > Any hints are welcome, If the graph is 3-connected, the embedding is unique once the outward face is fixed. In other words: the embedding on the sphere is topologically unique. I think this was first proofed by Whitley. The result is well-known and surely can be found in textbooks. Given this, derivation of an upper bound should be no problem. -- //// Olaf Delgado Friedrichs, Bielefeld, Germany `=' --- http://www.mathematik.uni-bielefeld.de/~delgado --- ============================================================================== From: Marcus Raitner Subject: Re: Number of embeddings of planar graphs Date: 4 Feb 2000 04:00:15 -0600 Newsgroups: sci.math.research Christoph Dornheim writes: > Hello, > > does anyone know how many topologically different embeddings a planar > graph can have (2^n or more)? Is there a least upper bound known in the > literature ? > Well, I think that a planar embedding is unique for 3-connected graphs. For 2-connected graphs you will get different embeddings by switching the 3-connected components around every separation pair. This is why you can have 2^|V| many different embeddings. Consider the following example: * /|\ / | \ / | \ * * * \ | / \ | / \| / * every permutation of the vertices in the middle is a different embedding. Clearly you can extend this example to any size. Hope this helps, Marcus Raitner -- -------------------------------------------------------------- Marcus Raitner Lst. Prof. Brandenburg raitner@fmi.uni-passau.de Uni Passau, D-94030 Passau ++49/851/509-3034, FAX: 3032