Opened 14 years ago

Closed 14 years ago

#1320 closed enhancement (fixed)

[with patch, positive review] planarity testing

Reported by: jason Owned by: ekirkman
Priority: major Milestone: sage-2.10.3
Component: graph theory Keywords:
Cc: bober Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Attachments (1)

planarity.hg (71.2 KB) - added by rlm 14 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 14 years ago by jason

  • Summary changed from [graphs] planarity testing to graphs: planarity testing

comment:2 Changed 14 years ago by ekirkman

  • Owner changed from mhansen to 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.

comment:3 Changed 14 years ago by rlm

  • Component changed from combinatorics to graph theory
  • Keywords graphs removed

comment:4 Changed 14 years ago by bober

  • Cc bober added

Changed 14 years ago by rlm

comment:5 Changed 14 years ago by rlm

  • Summary changed from graphs: planarity testing to [with patch, positive review] planarity testing

comment:6 Changed 14 years ago by rlm

  • Milestone changed from sage-wishlist to sage-2.10.3

comment:7 Changed 14 years ago by 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

comment:8 Changed 14 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 2.10.3.rc0

Note: See TracTickets for help on using tickets.