Ask Your Question
1

Find 25-vertex 4-regular planar graphs using plantri

asked 2021-03-27 03:55:43 +0200

licheng gravatar image

updated 2021-03-27 14:14:39 +0200

slelievre gravatar image

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?

Thanks in advance！

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 flag offensive close merge delete

Comments

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.

slelievre gravatar imageslelievre ( 2021-03-27 14:09:39 +0200 )edit
add a comment

1 Answer

Sort by » oldest newest most voted
2

answered 2021-03-27 14:47:58 +0200

David Coudert gravatar image

updated 2021-03-27 14:59:18 +0200

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='')

    for G in graphs._read_planar_code(sp.stdout):
        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).

edit flag offensive delete link more

Comments

Ticket ?

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

@David Coudert Thank you very much for your help

licheng gravatar imagelicheng ( 2021-03-27 15:48:48 +0200 )edit

Ticket:

slelievre gravatar imageslelievre ( 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.

licheng gravatar imagelicheng ( 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.

licheng gravatar imagelicheng ( 2021-03-28 15:53:01 +0200 )edit
see more comments

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

subscribe to rss feed

Stats

Asked: 2021-03-27 03:55:43 +0200

Seen: 343 times

Last updated: Mar 27 '21

Related questions

Generate certain number of planar graphs with graphs.planar_graphs?

Determining Complete Bipartite Graphs

Determining Complete Multipartite Graphs (Specifically Tripartite)

Iterating over all non isomorphic connected graphs of given order

Graphs from inside a function

Non-orientable genus of a graph

Typeset latex in SMC

I keep losing my node labels on graph export

Compute perfect matchings in a graph

Generating graph families in Sage

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59