In this release of the Edge Addition Planarity Suite project, the libPlanarity graph library has been marked as a major version change that could break backward compatibility. We have removed some application-level functions that only belonged only in the Planarity wrapper application for the graph library. The new planarity executable contains the functions, and other consumers of libPlanarity, such as SageMath, call API functions and not the removed functions.
The most important functional addition in this release is the addition of Graph6 file format (G6) support. In prior years, this project was exhaustively tested by testing algorithm results from all graphs generated by a copy of the Nauty project’s makeg graph generator that had been included in the project. For licensing reasons, it had to be removed. By adding Graph6 file support, we can now test algorithms against all graphs generated by a separately-compiled instance of the new Nauty Traces geng program.
In addition to being able to test all graphs in a given Graph6 file, we extended support to the ability to transform graphs stored in files and in-memory strings to and from Graph6 format and this project’s adjacency list and adjacency matrix formats. We also added support for the output of randomly generated graphs and LEDA input graphs into a Graph6 output file.
The most important bug fix in this release is to the implementation of the K3, 3 homeomorphic subgraph search. On a small fraction of graphs containing a subgraph homeomorphic to K3, 3, the search reported a null result due to an error in a pattern matching function that has been repaired. To help ensure that no other such issues exist, an extensive test framework written in Python has been developed and now comprises about one-quarter of the project’s total code (Python is not needed to run planarity.exe nor use libPlanarity; it is used during development to assist in exhaustive reliability testing prior to a release).
The Edge Addition Planarity Suite distribution has also undergone a substantial software engineering refresh, including:
- Reorganizing the code from a flat directory to subdirectories reflecting the modular architecture of the project, as expressed on the Project Overview wiki page.
- Switch to the free Microsoft VS Code development platform (and sunset of development with Eclipse) to provide better cross-platform development and debugging support on Windows, Mac and Linux.
- Switch from the legacy MinGW32 to the well-maintained MinGW-w64 and MSYS2 tooling under Windows.
- Coding improvements to address compatibility with the upcoming GCC 15 release (request from Debian Linux).
- Addition of
pkg-configfile support to enable the graph library of the planarity project to be found more easily by other programs/libraries (request from SageMath).
Further details about the release may be obtained from the 64 closed issues labeled 4.0.
The additional release assets have the following SHA256 hash values:
planarity-4.0.0.0.tar.gz: DF3C86C32FD37B801079AEA7DE67675EFDEF12ADA557CBCAAE821E81B8DB438Dplanarity-4.0.0.0.Windows-Intel.zip: 455F3C529018BC14F2FA9FB70E96A11C2E963840D750CB11312BC2B67BC1E895planarity-4.0.0.0.MacOS-Silicon.zip: 4cd29d7c997ed295dd99a74258b208148b76c463e1d0786e4791336a9cef64d9