# Find 25-vertex 4-regular planar graphs using plantri

I am using SageMath 9.2 and I have recently wanted to add the optional package plantri. I found a link to a similar question before: Ask Sage question 52358 where a comment suggests this command:

sage: !sage -i plantri


An error occurred during the installation process that prevented it from proceeding.

    make[3345]: Entering directory '/opt/sagemath-9.2'
0 [main] make (45584) C:\Users\asus\AppData\Local\SageMath 9.2\runtime\bin
\make.exe: *** fatal error in forked process - ccalloc would have returned NULL
0 [main] make 15063 dofork: child -1 - forked process 45584 died unexpect
dly, retry 0, exit code 0xC0000142, errno 11
make[3345]: *** [Makefile:31: bootstrap] Error 127


My computer runs the Windows10 64-bit operating system. I don't know how to solve this installation problem.

In fact, the graph theory problem I encountered is as follows.

I 'd like to generate all 25-vertex 4 regular planar graphs that size of maximum face is 4. Of course it may not exist.

With the help of plantri, I think there should be no problem, because I saw James Preen's page on the degree-diameter problem, which contains the following paragraph.

Additionally, using plantri it has been established that there exist no 4-regular planar graphs with 28 vertices and similarly there are no 3-regular planar graphs with diameter 4 with between 20 and 30 vertices.

If someone has successfully installed it, can you help me see if there is such a graph?

sage: for G in graphs.planar_graphs(25, minimum_degree=4):
....:     if G.num_edges==50:
sage:        show(G)
sage: print("nofind")


The above codes may need improvement.

edit retag close merge delete

The limit on posting links is because of high levels of spam posting.

One workaround is to post the link in split form, for instance https:// example .com and then some moderator can edit your post to put it back together.

( 2021-03-27 14:09:39 +0200 )edit

Sort by » oldest newest most voted

The current interface of plantri is incomplete. Indeed, we cannot specify the number of edges or an upper bound on the size if a face. The following method should do what you want.

import subprocess

def foo(n):
"""
Iterator over planar graphs of order n, size 2n, minimum degree 4
and faces of size at most 4
"""
from sage.features.graph_generators import Plantri
Plantri().require()
if n < 6:
return

command = 'plantri -pm4c0e{}f4 {}'.format(2*n, n)

sp = subprocess.Popen(command, shell=True,
stdin=subprocess.PIPE, stdout=subprocess.PIPE,
stderr=subprocess.PIPE, close_fds=True,
encoding='latin-1')

sp.stdout.reconfigure(newline='')

if G.is_regular(4):
yield(G)


I'll let it run for n=25 and let you know if it finds solutions (it might take a very long time).

more

Ticket ?

( 2021-03-27 15:09:29 +0200 )edit

@David Coudert Thank you very much for your help

( 2021-03-27 15:48:48 +0200 )edit
( 2021-03-27 17:15:13 +0200 )edit

Unfortunately, I do not know the upper bound for total numbers for the graphs with order 25 and minimum degree 4. I did not find the corresponding data, otherwise we can estimate the time.

( 2021-03-28 04:36:02 +0200 )edit

@David Coudert Haha, I found the corresponding data. There are 51 graphs that meet the requirements, but I don't know whether the graph data can be queried. see https://oeis.org/A111361. I quite hope to get the specific 51 graphs. I read that the authors of this article also used plantri.

G. Brinkmann, O. Heidemeier and T. Harmuth. The construction of cubic and quartic planar maps with prescribed face degrees. Discrete Applied Mathematics 128: 541-554, (2003).

Maybe I should write an email to the professors.

( 2021-03-28 15:53:01 +0200 )edit