Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a general planar graph, with no pair of vertexes being joined by more than one edge.

Is there a upper limit of planer embeddings of such graph? That is, in how many ways maximum can such a graph admit planar embedding? for any subclass of such graphs? lower limit is one, obviously.

share|improve this question
How do you define two embeddings as being different? e.g., if you just move a vertex by an $\epsilon$ in some direction, is that a different embedding? –  Casteels Feb 21 '14 at 13:06
let us say, we enumerate the vertices, consider the isomorphisms, and if we delete to outer vertices (thus edges outer too), then we have a subgraph. Two such subgraphs, generated from two such isomorphisms, if not isomorphic themseves / contains different vertices to each other, then we will consider the original isomorphs, before producing the subgraphs, different –  Sean Feb 21 '14 at 13:14
*the outer vertices –  Sean Feb 23 '14 at 20:47
Sean, do you mean this by different: Let $G=(V,E,\Psi)$ be a finite planar graph, and $X_0$ and $Y_0$ planar embeddings of $G$ (where we identify $V$ and $E$ and $\Psi$ with their images under the embeddings). If $X_0,X_1,X_2,\ldots$ (respectively $Y_0,Y_1,Y_2,\ldots$) is a decreasing sequence of subgraphs of $X_0$ (respectively $Y_0$), where $X_i$ obtained from $X_{i-1}$ by deleting the outer face of $X_{i-1}$ and the incident edges in $X_i$ to the outer face for each $i\ge 1$, then say $X_0$ and $Y_0$ are members of inequivalent classes of isomorphic embeddings of $G$ if for any $i\ge 1$ –  user131035 Feb 23 '14 at 22:58
Generally any face can be made the outer face, and always also a mirror image, so at least 2F. But there can be more if there are there are multiple chains of two-edge vertices running between particular vertices, then these chains can have multiple orderings for a particular outer face / orientation. For graphs rich in these chains you should get something near factorial growth in the number of embeddings. –  Neil W Feb 24 '14 at 7:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.