The plantri (see http://users.cecs.anu.edu.au/~bdm/plantri/) is a program that generates certain types of graphs that are imbedded on the sphere. Exactly one member of each isomorphism class is output.
Recently I am using the plantri to obtain the graph data of the non-isomorphic 3-connected planar quadrangulations with 12 vertices. The isomorphism here refers to the abstract graph isomorphism.
An isomorphism of graphs $G$ and $H$is a bijection between the vertex sets of $G$ and $H$. ${\displaystyle f\colon V(G)\to V(H)}$ such that any two vertices $u$ and $v$ of $G$ are adjacent in G if and only if ${\displaystyle f(u)}$ and ${\displaystyle f(v)}$ are adjacent in $H$. This kind of bijection is commonly described as "edge-preserving bijection".
If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as ${\displaystyle G\simeq H}$.
But I can see from the help document of this plantri that the isomorphism it defines seems to be different.
So I'm worried whether it's giving me all non-isomorphic 3-connected planar quadrangulations with $n$ vertices.
In defining "isomorphism" for two imbedded graphs, we have the choice of whether or not to automatically regard a graph and its mirror image as isomorphic. plantri knows both definitions:
Let $G$ and $H$ be two connected imbedded graphs with the same numbers of vertices and the same number of edges.
An ORIENTATION-PRESERVING (O-P) ISOMORPHISM from $G$ to $H$ is a bijection $f_v$ from $V(G)$ to $V(H)$, and a bijection fe from $E(G)$ to $E(H)$, such that
(1) If $e = \{v_1,v_2\}$ is in $E(G)$, then $f_e(e) = \{f_v(v_1),f_v(v_2)\}$ and $f_e(e)$ is in $E(H)$.
(2) If $(e_1,e_2,...,e_k)$ is the set of edges incident with a vertex $v$ of $G$, in clockwise order, then $(f_e(e_1),f_e(e_2),...,f_e(e_k))$ is the set of edges incident with the vertex $f_v(v)$ of G, in clockwise order.
An ORIENTATION-REVERSING (O-R) ISOMORPHISM from $G$ to $H$ is a bijection $f_v$ from $V(G)$ to $V(H)$, and a bijection $f_e$ from $E(G)$ to $E(H)$, such that
(1) If $e = \{v_1,v_2\}$ is in $E(G)$, then $f_e(e) = \{f_v(v_1),f_v(v_2)\}$ and $f_e(e)$ is in $E(H)$.
(2) If $(e_1,e_2,...,e_k)$ is the set of edges incident with a vertex $v$ of $G$, in clockwise order, then $(f_e(e_1),f_e(e_2),...,f_e(e_k))$ is the set of edges incident with the vertex $f_v(v)$ of G, in anti-clockwise order.
The MIRROR IMAGE of an imbedded graph is obtained by reversing all the cyclic orders. That corresponds to turning the sphere inside out.
The mirror image of the above graph is
An ISOMORPHISM from $G$ to $H$ is either an O-P isomorphism or an O-R isomorphism. Isomorphism and O-P isomorphism (but not O-R isomorphism) are equivalence relations, so we can speak of ISOMORPHISM CLASSES and O-P ISOMORPHISM CLASSES.
So I saw data of numbers of 3-connected planar quadrangulations like this:
More details see this web http://users.cecs.anu.edu.au/~bdm/plantri/plantri-guide.txt
My questions are the following:
-
- Are the graphs with $n$ vertices obtained by ISOMORPHISM definition from plantri mutual abstract non-isomorphism?
-
- If the graph is 3-connected, there are exactly two embeddings (which are equivalent if we allow orientation-reversing flips). This is a celebrated theorem of H. Whitney. I feel that the O-P non-isomorphic graph class should be twice the number of all non-ISOMORPHISM class. But we don’t think so from the data. When $n=8$, the number of nonisomorphic planar quadrangulations and O-P non-isomorphic planar quadrangulations are all equal to 1. And when $n=14$, the number of nonisomorphic planar quadrangulations are $11$, however the number of O-P non-isomorphic planar quadrangulations are $15$. $15 \ne 2\times 11$.
I'll use the unique 3-connected planar quadrangulation with 8 vertices as an example.
The right is the mirror image of the left. They don't seem to be op isomorphic. So as you can see in the picture below 1 should be corrected to 2, right?
I feel that there is a problem with my understanding of graph embedded isomorphism from plantri software.
