New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
use Brinkmann's algorithm to calculate the genus of a graph #29724
Comments
comment:1
From: Gunnar Brinkmann Re: open source version of multi_genus for sagemath? To: Dave Morris Dear Dave, you wrote
Sure, the program is attached. It reads multi_code. The format is very Feel free to use it in sage or in any other way where it can be useful. Best wishes, Gunnar |
comment:2
As mentioned in Professor Brinkmann's email message, the command-line version of the program reads
|
Branch: public/29724 |
comment:4
This PR puts the unaltered (but renamed) original source file into the Todo: 1. Implement an interface with sage. 2. Incorporate this into sage's New commits:
|
Commit: |
comment:5
Oops. The email in comment:1 was copied from the wrong screen, so it did not include the date. Here it is, for the record. From: Gunnar Brinkmann Re: open source version of multi_genus for sagemath? Date: May 21, 2020 at 12:09:25 AM MDT To: Dave Morris Dear Dave, you wrote
Sure, the program is attached. It reads multi_code. The format is very easy and described in the attached txt file. Feel free to use it in sage or in any other way where it can be useful. Best wishes, Gunnar |
comment:7
This is certainly a good idea to add an interface to this code, but, I think the right way to do it is to make an optional package, as we have for Not sure of the right link to get complete instructions to do that, but you can start with https://doc.sagemath.org/html/en/developer/packaging.html and https://wiki.sagemath.org/SageMathExternalPackages |
comment:8
Thanks for the suggestion. I have been busy in the past few weeks, but I will try to work on this ticket (and others) soon. |
comment:10
Setting new milestone based on a cursory review of ticket status, priority, and last modification date. |
Arxiv preprint 2005.08243 of Gunnar Brinkmann describes an algorithm for computing the genus of a graph. Professor Brinkmann sent me the C source code and gave permission to include it in sage. (I will paste the permission email into a comment so we have in on record.) This ticket will incorporate Brinkmann's algorithm into sage, either replacing or complementing the current algorithm.
In my limited command-line testing (and the testing reported in the preprint) it can be orders of magnitude faster than the algorithm that is currently in sage. For example, sage would take hours (or days?) to calculate the genus of the complete graph on 7 vertices (see
sage.graphs.genus.simple_connected_genus_backtracker?
), but Brinkmann's algorithm seems instantaneous for this graph. In fact, Brinkmann's algorithm is still instantaneous for complete graphs on 11 vertices, and takes only a few seconds for 13 vertices.CC: @dcoudert
Component: graph theory
Keywords: genus, topological graph theory
Branch/Commit: public/29724 @
c51d662
Issue created by migration from https://trac.sagemath.org/ticket/29724
The text was updated successfully, but these errors were encountered: