Given: A planar undirected connected graph $G$ in which degree of every vertex is $2$ or more.

Fact: A planar graph can have multiple planar embeddings.

Question: Give an efficient algorithm to find the set $S$ of face cycles corresponding to any one of the planar embeddings. We do not care about from which specific embedding $S$ is made from.

For example, a graph $G$ has the following two planar embeddings:

Two Embeddings

The above illustration shows two of may be several other planar embeddings of the same graph.

S for Embedding1: $\{ CDFC, ABDCA, ACEA, BDEB, ABEA, DEGD \}$

S for Embedding2: $\{ CFDC, CDGEC, DEGD, EBDE, ECAE, EABE \}$

S for EmbeddingN: $\{ ... \}$

We want our algorithm to return any one of the above sets.

  • 2
    $\begingroup$ de Fraysseix, H.; Pach, J; and Pollack, R. "Small Sets Supporting Fáry Embeddings of Planar Graphs." Proc. of the 20th Symposium on the Theory of Computing. ACM, pp. 426-433, 1988. $\endgroup$
    – user16034
    Jul 17, 2023 at 10:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.