Uniquely Embeddable Graph -- from Wolfram MathWorld

In general, different embeddings of the same planar graph can yield nonisomorphic dual graphs. A uniquely embeddable graph is a planar graph that has a unique dual graph up to isomorphism regardless of the underlying embedding used to construct it.

Two embeddings of a planar graph are equivalent if there is a homeomorphism of the sphere sending one drawing to the other. A uniquely embeddable graph therefore has all its embeddings on the sphere homeomorphic to one another.

Whitney (1932) proved that polyhedral graphs are uniquely embeddable.

The numbers of uniquely embeddable connected graphs on , 2, ... vertices are 1, 1, 2, 6, 15, 51, 206, 1297, 11742, 143095, 2056120, 32337106, ... (OEIS A372853), the first few of which are illustrated above. The largest numbers of planar embeddings for graphs on , 2, ... vertices are 1, 1, 1, 1, 2, 6, 24, 80, 240, 1080, 3780, 13440, ... (OEIS A372854).

Because some trees have branches that cannot be interchanged homeomorphically around a common fork, not all trees are uniquely embeddable. The smallest not uniquely embeddable tree has 7 vertices, and there is exactly one such tree. It is not uniquely embeddable because the two short branches can be either adjacent or between the two long branches, giving two distinct planar embeddings. There are four 8-vertex trees that are not uniquely embeddable, including the 4-centipede graph. The numbers of not uniquely embeddable trees on , 2, ... vertices are 0, 0, 0, 0, 0, 0, 1, 4, 16, 49, 140, 390, ... (OEIS A378673), with the corresponding number of uniquely embeddable trees given by 1, 1, 1, 2, 3, 6, 10, 19, 31, 57, 95, 161, ... (OEIS A378672).

Fleischner (1973) found a characterization of uniquely embeddable graphs for labeled graphs. A connected planar graph (involving labeling in some way) is uniquely embeddable in the plane iff is one of the following graphs: