TOPICS
Search

Uniquely Embeddable Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A uniquely embeddable graph is a planar graph whose embeddings on the sphere are all equivalent under a homeomorphism of the sphere sending one drawing to the other. The vertices are not fixed labels, so such a homeomorphism may induce a graph automorphism.

Every uniquely embeddable graph has a dual graph unique up to isomorphism, but this condition alone is not sufficient for unique embeddability.

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

UniquelyEmbeddableGraphs

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

NotUniquelyEmbeddableTrees

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 n=1, 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) used a stronger notion of equivalence for labeled graphs, distinct from the sphere homeomorphism convention above. The following characterization is for that stronger notion: a connected planar graph G 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_3 union K_2 with K_3 intersection K_2=v in V(G) and degv=3.

See also

Dual Graph, Homeomorphic Graphs, Planar Graph 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, A372854, A378672, and A378673 in "The On-Line Encyclopedia of Integer Sequences."Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Referenced on Wolfram|Alpha

Uniquely Embeddable Graph

Cite this as:

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

Subject classifications