We develop a graph editor and a C++ algorithm library essentially concerned with planar graphs. The
editor is particularly intended for graph theoretical research.
Pigale is available under the GPL license.
The source files and a Windows executable (under the non-commercial Qt license)
can be obtained either by ftp or cvs at SourceForge.
It is built over a new graph data structure optimizing topological operations on static graphs.
The graphml input-output file format is partially implemented.
We also provide a Client/Server which allows, among other things, to easily interface Pigale
with other programs (using a pipe).
The library includes the following new algorithms based on recent theoretical researches of our site.
General Algorithms:
a planarity test and an embedding computation algorithm using Fraysseix-Rosenstiehl left-right algorithm
[3,5,6]
(probably the fastest planarity test [27]),
a linear time algorithm to locate a Kuratowski subdivision or a cotree critical partial subgraph in a non planar
graph [4,21,24],
a linear time 3-connexity test for planar graphs [19,20],
a linear time recognition algorithm for subdivisions of 3-connected planar graphs ([19]),
a linear time 4-connexity test for maximal planar graphs [19],
a fast Depth-First Search algorithm (unpublished),
fast bipolar and regular orientation algorithms for planar graphs [16],
a linear time optimal triangulation algorithm for 3-connected planar graphs increasing the degrees by at most 6
[15],
a partitioner algorithm based on factorial analysis [13].
Drawing Algorithms:
optimized Fary drawing algorithms [8-11] relying on new planar augmentation algorithms [15], i.e.:
Fraysseix, Pach Pollack algorithm,
Schnyder algorithm using our triangulation algorithms,
Schnyder algorithm using a vertex triangulation,
Tutte barycentric representation of 3-connected graphs,
A Fary representation derived from the Tutte algorithm,
A spring embedder which preserves the map, (unpublished).
visibility representation of planar graphs [7],
a drawing of planar graphs using Béziers curves (based on a spring embedder, unpublished),
an algorithm to represent 2-connected planar bipartite graphs as the incidence graph of horizontal and vertical
segments [12,16],
an algorithm to represent planar graphs by contacts of T [14],
An algorithm to represent a graph in R3, as projections of different embeddings of the
graph in Rn-1 [13].
Experimental Algorithms:
an heuristic to detect symmetries [18],
an heuristic to find a maximal planar partial graph of a non planar graph (unpublished).
We are also adding some algorithms developed in other research centers:
Gilles Schaeffer:
random planar maps generators [17],
Nicolas Bonichon:
random outer planar maps generators [25],
drawing of planar graphs on the grid using polylines [22],
convex drawing of 3-connected planar graphs on the grid [26].
M. Matsumoto and T. Nishimura:
Equidistributed Uniform Pseudo-Random Number Generator [29],
The editor is based on the Qt library and uses the OpenGLlibrary for graph representations in
R3.
Some main features of this editor are:
