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].
The editor is based on the Qt library and uses the OpenGLlibrary for graph representations
in R3.
Some main features of this editor are:
- constrained drawing on a grid,
- unbound number of undoes,
- macro capabilities,
- reconfigurability.
Last modified: Wed Apr 20 19:16:23 CEST 2005