OGDF - Open Graph Drawing Framework

License: GNU General Public License version 3.0 (GPLv3)

Web Page: http://www.ogdf.net/doku.php/gsoc2014-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

• Basic Linear Algebra Support The goal of this project is to provide powerful and efficient vector and matrix classes, that provide the obvious basic functionality as well as more complex operations and different storage models.
• Computation of Treewidth Treewidth is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves to be useful in solving problems which were earlier known to be difficult. The goals of the project are to 1) Constructing an efficient data-structure for storing tree decomposition. 2)Implementing some efficient tree-decomposition heuristics. 3)Some sample applications (e.g Independent set).
• Preprocessing for Steiner Tree Problems The Steiner Tree problem consists of connecting a set of required vertices in a weighted graph at minimum cost. Although the Steiner Tree problem is NP-hard, it can be solved efficiently in practice. One main reason is the existence of powerful preprocessing methods able to reduce the instance size.
• Python Bindings for OGDF I will implement Python bindings for OGDF using SWIG, and write a tutorial for it.
• Search Trees and Priority Queues The goal of this project is clearly separate abstract data types (like priority queues and dictionaries) from implementing data structures, and identifying and providing various implementing data structures (some are already in OGDF and just need to be adapted, others like different kinds of balanced search trees and heaps have to be implemented from scratch).