planarity testing

[jasongrout]

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.

CC: @sagetrac-bober

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/1320

[f5e8177f-4f83-46ea-afc6-3b1cec5ec5bb]

comment:2

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.

[89c6e537-b2e3-45e6-882d-d4957b74ffe5]

comment:5

Attachment: planarity.hg.gz

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:7

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

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:8

Merged in Sage 2.10.3.rc0