Module and Graph method for Projective planarity via forbidden minors

[juan-mlr]

Addresses #37937 (to enable checking if a graph in projective planar) by

1. creating a new module, src/sage/graphs/projective_planarity.py, that holds the relevant forbidden minors and a function to search for them in another graph.
2. adding is_projective_planar method to Graph.

:memo: Checklist

• [x] The title is concise and informative.
• [x] The description explains in detail what this PR is about.
• [x] I have linked a relevant issue or discussion.
• [x] I have created tests covering the changes.
• [x] I have updated the documentation and checked the documentation preview.

:hourglass: Dependencies

[github-actions[bot]]

Documentation preview for this PR (built with commit 2849c51186a186aa74ab983e9ee2a9b9d72d0109; changes) is ready! :tada: This preview will update shortly after each push to this PR.

[steveschluchter]

@dcoudert can you comment on how we should declare this file in meson.build? It's just a python file with no cython or c to go with it.

you will have to declare the new file in src/sage/graphs/meson.build and in src/doc/en/reference/graphs/index.rst

[dcoudert]

@dcoudert can you comment on how we should declare this file in meson.build? It's just a python file with no cython or c to go with it.

you will have to declare the new file in src/sage/graphs/meson.build and in src/doc/en/reference/graphs/index.rst

open file src/sage/graphs/meson.build and add the name of the file in the block py.install_sources(...)

[steveschluchter]

@dcoudert

Can you help us avoid the circular import problem?

These lines appear in projective_planarity.py, and we're trying to keep the bulk of the code for the projective planarity check in a separate file.

from sage.graphs.graph import Graph from sage.graphs.generators.basic import ( CompleteGraph, CompleteBipartiteGraph, CompleteMultipartiteGraph, CycleGraph )

We could also presumably put the code in the graph.py file, but that's presumably not the way you want it done.

[steveschluchter]

@dcoudert thank you for your comments. We have made a new merge into this PR.

[steveschluchter]

@dcoudert We addressed your latest comments. Thank you for your thoughts.

[steveschluchter]

@dcoudert We have acted on your latest comments. Thank you for your thoughts.

[steveschluchter]

@dimpase Do you need anything else from us?

[dimpase]

@dcoudert sorry, I didn't mean to approve this.

[dcoudert]

@dimpase, can you try again to trigger CI runs ?

[dimpase]

I cannot - @roed or @saraedum can, but they are busy, and on the other hand reluctant to give such rights to e.g. me or you.

[dcoudert]

My main concern is that method is_projective_planar is extremely slow (that's why we must add a # long time tag to a doctest). Searching for minors is a difficult problem. Do you know any (faster) combinatorial algorithm ?

sage: P = graphs.PetersenGraph()
sage: %time P.is_projective_planar()
CPU times: user 2min 51s, sys: 642 ms, total: 2min 52s
Wall time: 2min 52s
True
sage: K44 = graphs.CompleteBipartiteGraph(4, 4)
sage: %time K44.is_projective_planar(return_map=True)
CPU times: user 2.12 s, sys: 11.5 ms, total: 2.13 s
Wall time: 2.13 s
(False, {0: [0], 1: [1], 2: [2], 3: [3], 4: [4], 5: [5], 6: [6], 7: [7]})

[dimpase]

can this be computed via combinatorial embeddings?

[steveschluchter]

@dcoudert @dimpase

I don't know of any other implemented projective planarity algorithm.

This work is related to a research project that @juan-mlr and I are doing, which is a continuation of https://combinatorialpress.com/article/jcmcc/Some-Excluded-Minors-for-the-Spindle-Surface.pdf for the projective plane.

Thank you very much for your thoughtfulness.

[dimpase]

https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/genus.html lets you compute the (oriented) genus of a graph, and it's reasonably fast on small graphs. If I understand this well, it's helpful in deciding the non-oriented genus, as it gives you Euler characteristic.

[dcoudert]

There is also this paper by Mohar https://doi.org/10.1006/jagm.1993.1050 https://www.sfu.ca/~mohar/Reprints/1993/BM93_JA15_Mohar_ProjectivePlanarity.pdf However, it might not be easy to implement.

Let us finish this PR. We can let the implementation of a faster method in the TODO list.

[steveschluchter]

Is there anything else we need to do? @dcoudert

[steveschluchter]

@dcoudert thank you for staying with me on this PR through each commit. I'd like to see the Mojar paper get implemented. Perhaps I'll have time in the future. That sounds like a nice challenge.

[vbraun]

sage -t --warn-long 30.0 --random-seed=123 src/sage/graphs/generators/families.py  # 2 doctests failed

[dcoudert]

For some reason, the code of method p2_forbidden_minors is inside de code of method petersen_family. Indeed, method DeltaYTrans and YDeltaTrans are sub-methods of petersen_family and are followed by some code of that method. Please move the code of method p2_forbidden_minors at a correct place, i.e., outside.

Sorry Volker for not seing that before. Not easy to work without CIs.

[steveschluchter]

I'm sorry about the mistake. I should have caught that one. I've made another push. Thank you for your comments and support.

[steveschluchter]

Thank you @dcoudert for helping us through this. Is there anything else you need?

[dcoudert]

Now that this PR is done, it would be nice to implement a faster algorithm (in a future follow up PR)

[steveschluchter]

Thanks for the vote of confidence @dcoudert. I thought this wasn't done becuase it was still open. We'll see about implementing Mojar's algorithm. That's going to be quite a haul.