TOPICS
Search

Uniquely Embeddable Graph


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.

UniquelyEmbeddable

The numbers of uniquely embeddable connected graphs on n=1, 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 n=1, 2, ... vertices are 1, 1, 1, 1, 2, 6, 24, 80, 240, 1080, 3780, 13440, ... (OEIS A372854).

NonuniquelyEmbeddableTree

Not all trees are uniquely embeddable; the unique smallest three that is not uniquely embeddable has 7 vertices and is illustrated above. There are four 8-vertex trees that are not uniquely embeddable, including the 4-centipede graph.

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

1. G is homeomorphic to a 3-connected graph,

2. G is homeomorphic to the complete bipartite graph K_(2,3),

3. G is homeomorphic to the triangle graph K_3,

4. G is homeomorphic to K_2 or G=K_1,

5. G is homeomorphic to K_(1,3), or

6. G is homeomorphic to K union K_2 with K_3 intersection K_2=v in V(G) and degv=3.


See also

Graph Dual, Homeomorphic Graphs, Planar Embedding

Explore with Wolfram|Alpha

References

Fleischner, H. "The Uniquely Embeddable Planar Graphs." Disc. Math. 4, 347-358, 1973.Sloane, N. J. A. Sequences A372853 and A372854 in "The On-Line Encyclopedia of Integer Sequences."Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Cite this as:

Weisstein, Eric W. "Uniquely Embeddable Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UniquelyEmbeddableGraph.html

Subject classifications