[with patch, positive review] planarity testing

[jason]

From Chris Godsil's wishlist.

>>> Someone is eventually going to ask for a routine to test for planarity. I
>>> believe that there are good ones in existence, but it's going to be
>>> hard to get
>>> a good one with an open source licence.
>> The nauty README has this to say about the new planarity testing feature:
>> "New program planarg to test for planarity and find planar embeddings:
>> planarg -help for details. The planarity code was written by Paulette
>> Lieby for the Magma project and used with permission."
>>
>> Does anyone know Paulette Lieby? Can we ask about releasing the code
>> under GPL? It looks like the source has now been released as a part of
>> nauty.
> Emily Kirkman understands a linear time algorithm for testing for
> planarity. There is one in BOOST, which is GPL, and has been nominated
> for inclusion in Sage several times.

[ekirkman]

I plan to begin implementing the Boyer-Myrvold linear time planar test/embedding algorithm right after autumn quarter finals. (Dec 13th). It should be available in early January.

[mabshoff]

Hi, I had a single, easy to fix merge conflict:

<<<<<<< /scratch/mabshoff/release-cycle/sage-2.10.3.rc0/devel/sage-main/sage/graphs/graph.py.orig.1734827483
from sage.graphs.graph_coloring import chromatic_number, chromatic_polynomial
||||||| /tmp/graph.py~base.vsk2R5
=======
from sage.rings.rational import Rational

The above was caused by the work on the chromatic number and chromatic polynomial by Tom.

Cheers,

Michael

[mabshoff]

Merged in Sage 2.10.3.rc0