Open Graph Drawing Framework
current version:
v.2015.05 (Baobab)

Google Summer of Code™ 2013

OGDF has been accepted as a mentoring organization for the Google Summer of Code™ (GSoc) 2013!

Student applications period (March 26 – April 6) is already over, and decisions on accepted applications have been made. Accepted students have been announced on the GSoC web page.

There is a special area for accepted students, with some in-depth information and pages for reporting progress. (restricted access)

Accepted Projects

Multi-Layer Crossing Minimization

OGDF's Sugiyama algorithm for hierarchical graphs implements the classical approach for crossing minimization, where crossings are iteratively (layer-by-layer sweep) minimized between neighbored layers (two-layer crossing minimization). However, recently this approach has been extended to consider “more layers at once” and to even allow nodes to change their layer if this saves crossings. Experimental results show that this approach can lead to much better results. Aim of this project is to implement these algorithms for k-layer crossing minimization and to make them available in OGDF's Sugiyama layout algorithm.

Student: Paweł Schmidt (University of Wrocław, Poland)
Mentors: Carsten Gutwenger, Robert Zeranski

Links: Original Project Idea

Efficient Optimal Bend Minimization

Though the bend minimization problem for 4-graphs (vertex degree bounded by 4) is in general NP-hard, it can efficiently be solved if we assume that the first bend is for free (does not cost anything). This has been shown in a recent paper by Bläsius, Rutter and Wagner. In fact, they even consider convex cost functions for the bends on an edge. The goal of this project is to implement their algorithm and integrate it into OGDF's framework for orthogonal graph drawing.

Student: Dzmitry Sledneu (Lund University, Sweden)
Mentors: Carsten Gutwenger, Markus Chimani

Links: Original Project Idea

Node Overlap Removal

While some graph layout algorithms naturally avoid node overlap due to the way they compute a layout, most instances of the most popular algorithmic approach, force-directed layout methods, due not take care of this problem automatically. Thus, resulting layouts of these methods may exhibit a large number of overlaps that make it difficult to perceive the graph's structure well and to nicely identify individual nodes. There however exists methods that allow to remove node overlaps in an existing layout without compromising the layout quality much. These can be run as a postprocessing step after a layout method that are prone to creating node overlaps.

Student: Anurag Murty (IISC Bangalore, India)
Mentors: Karsten Klein, Stephan Beyer

Links: Original Project Idea

Adding Support for Widely Used Graph File Formats

GraphML is an XML-based file exchange format widely used in the graph drawing community. The DOT file format (used by GraphViz) is designed such that it easily allows a user to write a simple text file describing the graph that shall be drawn. Though OGDF supports various file formats for graphs and graph layouts, these popular formats are not yet supported. The goal of this project is to add read and write support for both formats within the OGDF. As a regarded bonus, the student may also implement read (and write) support for other file formats like Gephi's XML-based GEXF, GUESS' CSV-alike GDF, UCINET's flexible DL or Tulip's s-expression-based TLP format.

Student: Łukasz Hanuszczak (University of Wrocław, Poland)
Mentors: Stephan Beyer, Robert Zeranski

Links: Original Project Idea

Porting OGDF to the Web

Graphs are everywhere on the Web, but great graph libraries written in JavaScript aren't. One way to deal with this misery is compile OGDF using Emscripten to JavaScript. Aim of this project is to set up OGDF to compile using Emscripten and make it run fast, and to create a nice demo page to play with.

Student: Saheb Motiani (Dhirubhai Ambani IICT, India)
Mentors: Christoph Schulz, | Markus Chimani

Links: Original Project Idea

Further Resources

gsoc2013.txt · Last modified: 2014/12/16 12:20 (external edit)
This page is driven by DokuWiki