All quadrangulations on $14$ vertices

141 Views Asked by At

I am looking for a list of all quadrangulations on $14$ vertices. Is there a database anywhere for this?

2

There are 2 best solutions below

2
On BEST ANSWER

We continue with the Steven's method, but as I commented, the Plantri software only considers outputting non-isomorphic embeddings, and may output isomorphic graphs when graphs have 1-cuts or 2-cuts (in the sense of abstract graph isomorphism). There are only 11 3-connected graphs, but there are still 14794 non-isomorphic quadrangulations with 2-cut sets. (Note that quadrangulations do not contain cut vertices.)

See all the 14805 quadrangulations with 14 vertices in my github.

Edits: We can see the definition of graph degeneracy from Wikipedia, which is as follows:

A $k$-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most $k$. The degeneracy of a graph is the smallest value of $k$ for which it is $k$-degenerate.

or: The degeneracy of a graph $G$, usually denoted $δ^∗(G)$, is the smallest integer $k$ such that the graph $G$ can be reduced to the empty graph by iteratively removing vertices of degree $≤k$

So if we want to specify which ones are not 2-degenerate of all of these quadrangulations, then we first note that the minimum degree of quadrangulations is $3$. We should first choose the option 14 -c2 in plantri, we will find 12 quadrangulations. There are 11 3-connected quadrangulations and one 2-connected quadrangulations with minimum degree 3.

1: MsTAA@_K?W_q?s?[?
2: MsTAB?oBGL?W?W?B_
3: MsT`@_HB?K?W?L?F?
4: Ms`IB?_K?o?b@k?w?
5: MsT`@_OAg[?W?W?D_
6: MsTB@_OBGK?W?W?F_
7: MsTB@?oC?W_w?[?B_
8: MsTaB?oBGI?o?o?B_
9: MsTAB?_K?W_e@g?w?
10: MsTAB?oBGJ?o?o?B_
11: MsTAB?_G@_@b@k?w?
12: MsTbA@_G@_@`?s?[?

By the following Python codes, I found that they are not 2-degenerate.

import networkx as nx
gl=nx.read_graph6('D:\\Users\\asus\\Q.g6') #your paths that stores the file Q.g6.
result = [g for g in gl if  max(nx.core_number(g).values())>2]
len(result)

enter image description here

5
On

The House of graphs has links to a lot of graph databases of all sorts. From there you will also find links to generators of many graph classes.
If with 'quadrangulations' you mean plane graphs having quadrangular faces, then you can find these here. You can also generate them with the program plantri by Brinkmann and McKay up to much higher order than 14.