Project info for Pigale

Created 3 Nov 2001 at 09:51 UTC by pom, last modified 7 May 2002 at 08:46 UTC by pom.

Freshmeat page: http://freshmeat.net/projects/pigale/

Notes:

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 and can be obtained either by ftp or cvs.

• Project page
• Installation
• Online Documentation
• Screen shots

It is built over a new graph data structure optimizing topological operations on static graphs.
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.
  • a linear time algorithm to locate a Kuratowski subdivision or a cotree critical partial subgraph in a non planar graph,
  • a linear time 3-connexity test for planar graphs,
  • a linear time recognition algorithm for subdivisions of 3-connected planar graphs,
  • a linear time 4-connexity test for maximal planar graphs,
  • a linear time optimal triangulation algorithm for 3-connected planar graphs,
  • a fast Depth-First Search algorithm,
  • fast bipolar and regular orientation algorithms for planar graphs,
  • a linear time algorithm for biconnecting planar graphs while preserving the embedding, which increases the degrees by at most 6 (optimal),
  • a linear time triangulation algorithm for 3-connected planar graphs increasing the degrees by at most 6 (optimal),
  • a partitioner algorithm based on factorial analysis.
• Drawing Algorithms:
  • optimized Fary drawing algorithms relying on new planar augmentation algorithms, i.e.:
    • 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,
  • an algorithm to represent 2-connected planar bipartite graphs by drawing two forests on two pages,
  • an algorithm to represent 2-connected planar bipartite graphs as the incidence graph of horizontal and vertical segments,
  • An algorithm to represent a graph in R3, as projections of different embeddings of the graph in Rn-1.
• Experimental Algorithms:
  • an heuristic to detect symmetries,
  • an heuristic to find a maximal planar partial graph of a non planar graph.

License: GPL

This project has the following developers:

• pom is a Lead Developer.
• hf is a Lead Developer.

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!