OGDF - Open Graph Drawing Framework

Web Page: http://www.ogdf.net/doku.php/gsoc2013-ideas

Mailing List: https://groups.google.com/group/ogdf

The Open Graph Drawing Framework (OGDF) is a C++ library of algorithms and data structures for graph drawing. OGDF’s goal is to help bridge the gap between theory and practice in the field of automatic graph drawing. The library offers a wide variety of algorithms and data structures, some of them requiring complex and involved implementations, e.g., algorithms for planarity testing and planarization, or data structures for graph decomposition. A substantial part of these algorithms and data structures are building blocks of graph drawing algorithms, and the  OGDF aims at providing such functionality in a reusable form, thus also providing a powerful platform for implementing new algorithms.

Our proposed projects range from extending the library (this requires programming in C++) to applications and new interfaces (some of those projects require a good knowledge of Python or Java).

Projects

• Adding Support for Widely Used Graph File Formats Though OGDF supports various file formats for graphs and graph layouts, couple of popular formats are not yet supported. The goal of this project is to add read and write support for formats such as: GraphML (XML-based), DOT (used by GraphViz), GEXF (Gephi's XML-based), GDF (GUESS CSV-alike), UNICET DL and TLP (used by Tulip).
• Efficient Optimal Bend Minimization I would like to implement the bend minimization algorithm for planar graphs with maximum degree 4, where the first bend on each edge is for free and the cost function of each edge is convex. The algorithm will be integrated into the orthogonal drawing framework.
• Multi-Layer Crossing Minimization Practical implementation of a few heuristics minimizing the number of edge crossings in planar representation of hierarchical graph that can be used in the Sugiyama framework for drawing such graphs.
• Porting OGDF to Web - OGDF.js Using Emscripten to convert present C++ OGDF code to Javascipt and make it available on the Web. Prepare good examples and demos for getting new users and contributors. In short, to make an easy to use Graph Drawing Library for the Web.