2
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ The files in your link are only 3-connected quadrangulations, and it seems that graphs containing 1-cuts or 2-cuts are not included. $\endgroup$
    – licheng
    Feb 11, 2023 at 8:05
  • $\begingroup$ Plantri only focuses on generating graph embeddings, and for the 3-connected situation, the embedding isomorphism and abstract graph isomorphism are consistent, but for vertex connectivity less than 3, the situation is essentially different. I generated 15,882 non-isomorphic embeddings with plantri. Further elimination of abstract isomorphic graphs is then necessary. $\endgroup$
    – licheng
    Feb 11, 2023 at 8:11
  • 1
    $\begingroup$ I think this strongly depends on the OP's interests. Personally I think having the embedded structures is more interesting. $\endgroup$
    – Steven
    Feb 12, 2023 at 20:49
  • 1
    $\begingroup$ Anyway, if you want all non-isomorphic non-3-connected cases, you can combine plantri with nauty to find the set of 14805 graphs: ./plantri 14 -q -c2m2 -g | ./nauty/shortg $\endgroup$
    – Steven
    Feb 12, 2023 at 20:51
  • $\begingroup$ Nice! Different embeddings are sometimes more interesting. I always use the following command to filter (./plantri 14 -c2m2 -q -g |./nauty/labelg|sort|uniq ). Your code is better. $\endgroup$
    – licheng
    Feb 13, 2023 at 2:01
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Hi, thanks. Could you specify which ones are not $2$-degenerate of all of these quadrangulations? $\endgroup$ Feb 14, 2023 at 17:03
  • $\begingroup$ @causalityrefilm. see new edit. $\endgroup$
    – licheng
    Feb 16, 2023 at 7:33

You must log in to answer this question.

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