use Brinkmann's algorithm to calculate the genus of a graph

[DaveWitteMorris]

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

[DaveWitteMorris]

comment:1

From: Gunnar Brinkmann

Re: open source version of multi_genus for sagemath?

To: Dave Morris

Dear Dave,

you wrote

Although I am not in the field of topological graph theory, I found your recent arxiv preprint to be very interesting. So I am writing to ask whether you are willing to release the source code of multi_genus under a GPL-compatible license (GPL v3 or later), so that it can be included in sagemath.

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

[DaveWitteMorris]

comment:2

As mentioned in Professor Brinkmann's email message, the command-line version of the program reads multi_code input. This format is described in the documentation of gconv by Thomas Harmuth.

4) multi_code_old
   This code is binary. The first entry is the number of vertices.
   Vertices are numbered 1,...,n. To each vertex x there is a list of
   neighbours with higher numbers than x (like in reg_code_old), followed by a zero.
   The last list is always empty (no neighbours of n with a higher number than n),
   so the last "list" is not followed by a zero.
   After the last byte the next graph follows.
        ...
7) multi_code
   See 4), but with the header at the beginning. The header is one of the following:
   >>multi_code<<
   >>multi_code le<<
   >>multi_code be<<
   where "le/be" stands for little endian/big endian.

[DaveWitteMorris]

Branch: public/29724

[DaveWitteMorris]

comment:4

This PR puts the unaltered (but renamed) original source file into the src/sage/graphs/ directory. It can be compiled for command-line use, by using the instructions at the start of the file.

Todo: 1. Implement an interface with sage. 2. Incorporate this into sage's genus method. I do not expect either of these to be difficult.

---

New commits:

c51d662

original multi_genus source file

[DaveWitteMorris]

Commit: c51d662

[DaveWitteMorris]

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

Although I am not in the field of topological graph theory, I found your recent arxiv preprint to be very interesting. So I am writing to ask whether you are willing to release the source code of multi_genus under a GPL-compatible license (GPL v3 or later), so that it can be included in sagemath.

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

[dcoudert]

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 tdlib, bliss, etc.

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

[DaveWitteMorris]

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.

[mkoeppe]

comment:10

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.