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: |
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)
Change History (9)
comment:1 Changed 14 years ago by
- Summary changed from [graphs] planarity testing to graphs: planarity testing
comment:2 Changed 14 years ago by
- Owner changed from mhansen to ekirkman
comment:3 Changed 14 years ago by
- Component changed from combinatorics to graph theory
- Keywords graphs removed
comment:4 Changed 14 years ago by
- Cc bober added
Changed 14 years ago by
comment:5 Changed 14 years ago by
- Summary changed from graphs: planarity testing to [with patch, positive review] planarity testing
comment:6 Changed 14 years ago by
- Milestone changed from sage-wishlist to sage-2.10.3
comment:7 Changed 14 years ago by
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
- 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.
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.