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

GSoC 2013 - Project Ideas

This page is for a Google Summer of Code program in the past. Do not apply for projects in this list!

Our project ideas for OGDF range from projects that shall improve its usability to projects touching topics of current scientific research in graph drawing. For all these projects, participating students should be interested in the visualization of graphs and have some theoretical background in graph algorithms.

This is a collection of project ideas we propose for GSoC 2013. Each project idea links to its detailed description below. If you have further project ideas and or want to discuss some of our proposed project please contact us by email (gsoc@ogdf.net), or directly contact the responsible mentor(s).

Please also refer to our GSoC FAQ for frequently asked questions.

Detailed Project Descriptions

Multi-Layer Crossing Minimization

Brief description: 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.

Expected result: An extended SugiyamaLayout module that supports general, k-layer crossing minimization modules (layer-by-layer sweep could be one such module) and modules that implement global crossing minimization algorithms (see literature below).

Rationale: OGDF's implementation of the Sugiyama framework is very flexible and provides various implementations for the different phases of the algorithm. Moreover, OGDF contains a new, sophisticated approach for drawing hierarchical graphs which is based on upward planarization. The latest scientific results show that, although upward planarization achieves the best results, more global k-level crossing minimization heuristics can come close and are much easier to implement. This project will enable us to integrate new algorithms and to perform a fair evaluation of the different approaches, which is of high interest both in theory and practice.

Literature:

Prerequisites: C++, Subversion, good knowledge in algorithms and data structures

Skill level: medium

Mentor: Carsten Gutwenger, Markus Chimani

Efficient Optimal Bend Minimization

Brief description: 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.

Expected result: An implementation of (a simplified version of) the bend minimization algorithm, where the first bend is for free and every additional bend costs 1. Integration of the implementation into the orthogonal drawing framework; in this framework, a general graph is planarized by putting dummy nodes on crossings (crossing minimization step), then this planar graph is transformed into a planar 4-graph, bend minimization is applied and the graph is drawn (coordinates are assigned, compaction step). As a bonus, the full algorithm (given a convex bend function for each edge) can be implemented.

Rationale: Since this algorithm optimizes over all embeddings of the graph, better results are expected then just using the trafitional approach, where Tamassia's bend minimization algorithm is applied on a graph with a fixed embedding.

Literature:

Prerequisites: C++, Subversion, good knowledge in graph algorithms and data structures

Skill level: high

Mentor: Carsten Gutwenger, Markus Chimani

Node Overlap Removal

Brief description: 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.

Expected result: In this project a selected method out of the existing node overlap removal strategies should be implemented.

Rationale: A node overlap removal can largely improve the quality of graph layouts from force-directed methods.

Literature: Emden Gansner, Yifan Hu: Efficient, Proximity-Preserving Node Overlap Removal, JGAA vol. 14, no. 1, pp. 53-74, 2010

Prerequisites: C++, Subversion, good knowledge in algorithms and data structures

Skill level: medium

Mentor: Carsten Gutwenger

Improved Packing of Connected Components

Brief description: If a graph is not connected, it is a wise idea to draw each component separately, and then arrange the resulting layouts for the components such that the area of the final drawing is minimized, or a desired aspect ratio is optimized. This problem can be seen as a packing problem of 2D-geometric objects. OGDF provides a simple algorithm for this task, which is used as a subroutine by many drawing algorithm. However, there are much more advanced techniques for solving such packing problems, e.g., Polyomino packing as proposed by Freivalds et al. The goal of this project is to implement advanced packing algorithms for connected components within the OGDF. Further own ideas are welcome. E.g., in some cases, components may also be rotated or nested.

Expected result: An implementation of the Polyomino Packing algorithm and other approaches / new ideas as a CCLayoutPackModule in OGDF.

Rationale: This shall improve the used drawing area for many layout algorithms if the graph contains many connected components.

Literature:

Prerequisites: C++, Subversion, good knowledge in algorithms and data structures

Skill level: medium

Mentor: Robert Zeranski, Stephan Beyer

Extending the Framework for Constraint-Based Drawing

Brief description: OGDF contains a powerful framework for the so-called constraint-based drawing, where a layout is not computed by an algorithmic approach that constructs the drawing, but a descriptive approach, where the requested features of the drawing are specified in form of constraints, and then a solver is used to solve the resulting system of constraints. This approach has found considerable attention in research recently, and it very interesting for layout computation in areas with a large number of requirements for the resulting drawing, e.g. network visualization in the life sciences. In the current state, the framework only supports a small number of constraints.

Expected result: The goal of this project is to add support for two further constrains to the set of constraints supported by the constraint-based framework in OGDF.

Rationale: This projects strengthens the constraint-based part of OGDF, making it better applicable for graph drawing in practice.

Prerequisites: C++, Subversion, good understanding of geometric principles and basic maths

Skill level: high

Mentor:

Python Bindings for OGDF

Brief description: Python bindings shall make some main functionality of OGDF (like graph objects, graph and layout algorithms) available for use in Python programs. One way to achieve this is by using SWIG, which even supports other target languages.

Expected result: A basic but extendable framework, providing some main functionality, including a tutorial on how to use it.

Rationale: Providing easy to use interfaces is crucial for every software library. Though OGDF provides a wealth of powerful data structures and algorithms, accessing them through C++ code is a big problem for many users. Making OGDF's functionality easily usable from a scripting based programming language like Python will not only make OGDF accessible for many more users, but also adds many benefits for experienced programmers.

Prerequisites: Python, C++, Subversion

Skill level: high

Mentor: …, Markus Chimani, Christoph Schulz

Adding Support for Widely Used Graph File Formats

Brief description: 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.

Expected result: Parsers for these file formats, extension of OGDF's GraphIO class by adding static functions for reading and writing graphs (Graph) and layouts (GraphAttributes) in these file formats.

Rationale: Improving the usability of OGDF by supporting many additional graph formats.

Prerequisites: C++, XML, Subversion

Skill level: easy/medium

Mentor: Christoph Schulz, Stephan Beyer, Robert Zeranski

Porting OGDF to the Web

Brief description: 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. Note: there is a license problem involved (GPL and JavaScript/WebPage “include”… very tricky)

Expected result: Setup OGDF to compile using Emscripten and make it run fast; nice demo page to play with.

Rationale: Provide sophisticated graph drawing capabilities directly in the web browser, thus targeting new application areas.

Literature: Zach Walton, Easily Port C++ To HTML5/JavaScript With Emscripten, WebProNews, iEntry Network, 2012

Prerequisites: C++, JavaScript, knowledge of LLVM and V8 internals are an advantage

Skill level: easy / medium (compiling is easy, optimizing for Emscripten is very tricky as VMs are a moving target)

Mentor: Christoph Schulz

Extending OGML support for Cytoscape

Brief description: OGML, the Open Graph Markup Language, is an open, XML-based, format to store graphs and their annotations. It has been developed in the OGDF project as a successor of the GML format in order to overcome the drawbacks of this outdated format, including the lack of mechanisms to store data annotations stemming from practical application areas and to specify advanced structural concepts like clusters. While OGML has a flexible extension mechanism, it still provides explicit basic features that allow to directly map properties needed in graph drawing, making it the format of choice when annotated networks need to be stored for visualization purposes. Though the format was developed within the OGDF project, it is an independent format that can freely be used within any other project to store or transfer graph or network data. Cytoscape is an open source platform for complex network analysis and visualization. Cytoscape allows to apply several automatic layout methods and features a number of export formats. There is a simple Cytoscape OGML plugin that allows to import/export basic features of a network, such as the nodes and edges. However, many features, including most of the features that control the visual appearance, as line style, and edge bends, are not handled. This leads to an annoying change in appearance e.g. when exported data is reimported.

Expected result: The goal of this project is to complete the OGML support for Cytoscape for all relevant features by adding the missing features to the import and export capabilities, an XML schema for OGML and a (non final) documentation of the basic structure are available.

Rationale: This projects combines the two open source projects OGDF and Cytoscape. It provides a useful extension to Cytoscape and at the same time facilitates to exchange complex network data together with relevant annotations, allowing easy access to OGDF's sophisticated layout methods.

Prerequisites: Java, XML, knowledge of Cytoscape and file parsing is an advantage

Skill level: easy/medium

Mentor: Karsten Klein

 
gsoc2013-ideas.txt · Last modified: 2015/05/05 16:42 by stephan
This page is driven by DokuWiki