6
$\begingroup$

Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ is planar if $G$ has an embedding in the plane. Two embeddings of a planar graph are equivalent when the boundary of a face in one embedding always corresponds to the boundary of a face in the other. We say that the plane embedding of a graph is unique when all the embeddings are equivalent.

Whitney proved that the embedding of a 3-connected planar graph is unique. However, when the connectivity of a planar graph is 1 or 2, this uniqueness cannot be guaranteed. For example, the left and right embeddings of the following graph are not equivalent. enter image description here

Another example,

enter image description here

So is there any research on counting the number of non-equivalent embeddings for given planar graphs or listing these embeddings?

In a practical sense, are there relevant program implementations ? I know that there are two nice programs, nauty and plantri, I have not seen them.

Interestingly, in the monograph Planar graph drawing ( T. Nishizeki), I see the following theorem; see Page 27.

Theorem 2.2.2 The embedding of a 2-connected planar graph $G$ is unique if and only if $G$ is a subdivision of a 3-connected graph.

However, even determining the uniqueness of embeddings through the analysis of whether $G$ is a subdivision of a 3-connected graph is not an easy task.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I would try to start with the following approach. Any embedding of your graph induces a cyclic ordering on the set of edges at each vertex (just go through them counterclockwise). Given an arbitrary choice of cyclic ordering on the neighboring edges at each vertex, one can reconstruct where the 2-cells must have been. Glueing them in always gives a surface (any edge appears twiice and each link of a vertex also looks ok). Now the question is whether that surface is a sphere or a torus or ... One could write a computer program that goes through all the choices of cyclic orders and computes $\endgroup$
    – HenrikRüping
    Commented Sep 15, 2023 at 12:02
  • $\begingroup$ the Euler characteristic of that surface and only pick the ones which are spheres. I believe two embeddings are equivalent, iff they induce the same or exactly the opposite cyclic orderngs (opposite to deal with mirror images). $\endgroup$
    – HenrikRüping
    Commented Sep 15, 2023 at 12:05
  • 3
    $\begingroup$ Neither nauty nor plantri can solve this problem. Starting with one embedding, you can reach all the others using three operations. At a cutpoint you can flip over (take the mirror image) of one of the components (not drawn), or you can move one of the components into one of the other faces that meet at the cutpoint (your first example). At a cut of two vertices, you can flip one of the components over (like in your second example). But counting the number of distinct results depends on symmetries so it gets messy. $\endgroup$
    – Brendan McKay
    Commented Sep 15, 2023 at 14:34
  • $\begingroup$ @BrendanMcKay Thanks. I know another software CaGe based on planari, which has option reset embedding. But this button often becomes unresponsive, even when there are more than one embedding of a given graph. $\endgroup$
    – Licheng Zhang
    Commented Sep 16, 2023 at 3:45
  • 1
    $\begingroup$ "reset embedding" goes back to the original embedding, so clicking it twice is the same as clicking it once. It doesn't mean to use a different embedding. You can put a face of your choosing on the outside by clicking in it, but there is no way to show all the embeddings of a graph that isn't 3-connected. $\endgroup$
    – Brendan McKay
    Commented Sep 16, 2023 at 5:11

3 Answers 3

Reset to default
4
$\begingroup$

As suggested by Henrik Rüping in the comments, this problem can be solved in principle using the representation of embeddings by permutations, i.e., using combinatorial maps (aka "rotation systems" aka "ribbon graphs"). Start by dividing every edge of your graph $G$ in two to define a set of labelled half-edges $D$ together with an involution $\alpha$ on $D$ taking each half-edge to its matching half. Next consider the partition $\lambda$ of $D$ defined by grouping together all of the half-edges incident to each vertex. Then every permutation $\sigma$ of $D$ with underlying partition $\lambda$ determines together with $\alpha$ an embedding of $G$ into some oriented surface, which will be planar just in case $cycles(\sigma) - cycles(\alpha) + cycles(\sigma\alpha) = 2$, by the Euler characteristic formula. So to enumerate all inequivalent planar embeddings it suffices to enumerate all such $\sigma$ and remove duplicates, where two maps $(\alpha,\sigma)$ and $(\alpha',\sigma')$ are equivalent just in case there is some relabelling $\pi$ of the half-edges such that $\pi\alpha = \alpha'\pi$ and $\pi\sigma = \sigma'\pi$.

In terms of practical implementations of combinatorial maps, I am not sure what is the state-of-the-art. Sage has a library for Ribbon Graphs, but it does not seem to include equivalence testing as far as I can tell. I wrote an equivalence testing routine as part of a small library of Haskell code for combinatorial maps, but I'm sure that there are better approaches. I suspect that the GAP system can be used to do this kind of enumeration much more efficiently.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ The problem is that for graphs of even modest size the number of combinatorial embeddings is vastly greater than the number which are planar. It is much more efficient to generate just the planar ones by the operations I listed in a comment above, which can be described in terms of $(\alpha,\sigma)$ if you wish. Consider cubic planar graphs, where there are exponentially many embeddings but as little as 2 that are planar. $\endgroup$
    – Brendan McKay
    Commented Sep 16, 2023 at 12:24
  • 2
    $\begingroup$ In terms of equivalence testing, there are linear-time algorithms but they are impractical. The map can be uniquely labeled with respect to a root flag by using DFS or BFS from that flag using the embedding to determine the order of visiting neighbours. Then a canonical form of the map is the lexicographically best of those labellings. With some heuristics to help, it can be made almost linear on average with a very small constant. $\endgroup$
    – Brendan McKay
    Commented Sep 16, 2023 at 12:33
  • $\begingroup$ Thanks for the comments and I completely agree that this approach will only work "in principle" for small graphs. So then the procedure you suggest (1. start with a planar embedding of the graph, 2. apply the flip/move operations in all possible ways, 3. remove duplicates using a DFS/BFS) would yield a much more efficient solution to the original question, wouldn't it? But you wrote that "Neither nauty nor plantri can solve this problem." Is it just that this specific functionality hasn't been implemented, although it could be implemented in principle? $\endgroup$
    – Noam Zeilberger
    Commented Sep 16, 2023 at 12:57
  • 1
    $\begingroup$ The labelling method I described is used internally in plantri, but it hasn't been developed into a program to solve this particular problem as far as I know. I find the approach somewhat unsatisfying because one has to keep the known planar maps in order to compare against them. Sometimes there could be quite a lot. A better solution would be to understand the symmetries of the original well enough to know in advance which other embeddings will be equivalent. But this sounds nontrivial. (continued) $\endgroup$
    – Brendan McKay
    Commented Sep 16, 2023 at 13:10
  • 2
    $\begingroup$ I had a student who solved a related problem, namely to generate planar graphs, up to usual graph isomorphism, by identifying the graph with a unique embedding out of all its planar embeddings. It was successful but very complicated. $\endgroup$
    – Brendan McKay
    Commented Sep 16, 2023 at 13:12
2
$\begingroup$

I had this same problem. I couldn't find any actually implemented code after a lot of looking, but I did find some papers describing how to do it.

The most promising was "A linear algorithm for embedding planar graphs using PQ-trees" by Norishige Chiba, Takao Nishizeki, Shigenobu Abe, and Takao Ozawa. It describes an algorithm to enumerate all planar graph embeddings of a given planar graph in linear time.

https://www.sciencedirect.com/science/article/pii/0022000085900042

Using algorithm GENERATE one can generate all the embeddings of G without duplications. (The proof is left to the reader.) It is also easy to decide the total num- ber of possible embeddings of G from the expression of A,.

In the intro they also say Hopcroft and Tarjan described a way to extend their planar testing algorithm to do the same, but that it was more complicated than the approach Chiba, Nishizeki, Abe, and Ozawa took.

I'm currently working on a paper and have some associated code that would benefit from enumerating all planar embeddings of arbitrary planar graphs, but rock solid proof that the enumeration is complete is not necessary for what I'm doing. I'm gonna bite the bullet and try to implement the algorithm described in the paper I linked using sage/python. If I'm feeling particularly ambitious I may try to include an explicit proof/fill in that detail, but chances of me doing that are extremely low/I'm intending to just implement what they describe on faith.

If you beat me to an implementation or find one already done before I finish this please let me know. I'll share my work here in a separate repo if and when I complete it.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ If I understand correctly, they claim an algorithm for finding one planar embedding of a planar graph in time $O(n)$ where $n$ is the number of vertices, and at the end of the paper they explain how to adapt the algorithm to generate all planar embeddings. But they do not claim the generation algorithm is linear time, which would run into difficulties with the size of the output since some planar graphs (such as trees) can have exponentially many embeddings. $\endgroup$
    – Noam Zeilberger
    Commented Sep 19, 2023 at 19:42
  • $\begingroup$ (nevertheless trying to implement their algorithm sounds like it could be a fun and useful project!) $\endgroup$
    – Noam Zeilberger
    Commented Sep 19, 2023 at 19:45
  • $\begingroup$ @NoamZeilberger, correct. Believe it's still linear relative to the size of the output, but yes, not the number of vertices. That's an important note, thank you. And yes, hopefully it's useful! Would be less fun if it turns out there's a better version out there somewhere/I'm reinventing the wheel, but is still a good exercise. $\endgroup$
    – didericis
    Commented Sep 19, 2023 at 20:45
2
$\begingroup$

(Too long for a comment). Note that there are two different ways to define "all the embeddings" of a graph, both completely natural. I'll illustrate by example. Suppose a graph consists of two triangles sharing one vertex.

By one definition, this graph has a unique embedding on the sphere:

enter image description here

(The drawing with one triangle inside the other is the same on the sphere.)

By another definition, this graph has two distinct embeddings:

enter image description here

Note that the two graphs are identical as labelled graphs, yet the labelled faces are not the same.

The theorem of Nishizeki cited by the OP refers to the second definition, and so does the algorithm of Chiba et al. I'm not sure which definition OP has in mind.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. What I often consider is the first type, unlabeled. Moreover, for $k$-planar graphs, this need will increase. For example, traverse different non-isomorphic 1-planar drawings of some graphs of low-order. (Two drawings of a graph are isomorphic if there is a homeomorphism of the sphere that maps one drawing to the other. ) $\endgroup$
    – Licheng Zhang
    Commented May 14 at 12:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .