Karsten Klein

Karsten Klein
	Address Chair of Algorithm Engineering Computer Science Department Dortmund University of Technology Otto-Hahn-Str. 14 44227 Dortmund Germany
	Contact Information
	Email:	Karsten.Klein <at> cs.uni-dortmund.de
	Phone:	+49 231 755-7707
	Fax:	+49 231 755-7740
	Room:	2.38

Research Topics | Teaching | Research | Projects | Publications

Research Topics

Graph Algorithms, (Clustered) Planarity Testing and Embedding
Algorithm Engineering, in particular for Graph Drawing methods
Graph Drawing, in particular Orthogonal Graph Drawing, Compaction Algorithms, Interactive Graph Drawing, Graph Drawing with Constraints, Layout of Clustered and Compound Graphs
BioInformatics, in particular visual analytics of networks
Combinatorial Optimization

InterDom Breast Cancer Protein Domain Network Layout

Projects

	Open Graph Drawing Framework (OGDF) The Open Graph Drawing Framework (OGDF) is an open source software project that provides a library of datastructures and graph layout algorithms. OGDF is the successor of AGD, the library of algorithms for graph drawing.
	Scaffold Hunter Scaffold Hunter is a tool for the interactive exploration of chemical space. It facilitates navigation by graphical visualization of structural relationships and provides methods for the analysis of large data sets, e.g., to correlate chemical structure and biochemical activity. Scaffold Hunter is implemented in Java and freely available under the GPL.

Open Graph Drawing Framework (OGDF)

The Open Graph Drawing Framework (OGDF) is an open source software project that provides a library of datastructures and graph layout algorithms. OGDF is the successor of AGD, the library of algorithms for graph drawing.

Scaffold Hunter Screenshot

Scaffold Hunter

Scaffold Hunter is a tool for the interactive exploration of chemical space. It facilitates navigation by graphical visualization of structural relationships and provides methods for the analysis of large data sets, e.g., to correlate chemical structure and biochemical activity. Scaffold Hunter is implemented in Java and freely available under the GPL.

Research

Conferences and Workshops (A link to Carsten Gutwenger's event collection)
A collection of interesting conferences and workshops in the field of combinatorial optimization.
Automatic Graph Drawing
Various links to books, conferences, people, etc. (maintained by Carsten Gutwenger).

Recent Publications

Analyzing and visualizing residue networks of protein structures
Nadezhda T. Doncheva, Karsten Klein, Francisco S. Domingues, and Mario Albrecht
Trends in biochemical sciences doi:10.1016/j.tibs.2011.01.002 (2011)
CT-Index: Fingerprint-based Graph Indexing Combining Cycles and Trees
Karsten Klein, Nils Kriege, and Petra Mutzel
27th IEEE International Conference on Data Engineering, Hannover (ICDE 11), to appear.
An Experimental Evaluation of Multilevel Layout Methods
Gereon Bartel, Carsten Gutwenger, Karsten Klein, and Petra Mutzel
18th International Symposium on Graph Drawing 2010, Konstanz (GD10), LNCS 6502, 80--91.

Teaching

Upcoming Teaching
WS 11/12
???	TBA

Current Teaching
WS 10/11+SS11
PG 552	Drug Hunting
Fachprojekt	Algorithm Engineering

Previous Teaching
SS 10
Effiziente Algorithmen	Übungen zu Effiziente Algorithmen
WS 09/10
EinI LW	Eini LW Wiki
WS 08/09+SS09
PG 534	Vehicle Routing
SS 08
PG 517	Evakuierungsprobleme
WS 07/08
Seminar	Seminar Algorithm Engineering
SS 07
PG 503	Xaver: Algorithm Engineering XXL
PG 504	ChemBioSpace Explorer
Seminar	Visualisierung in der Bioinformatik
Übung/VL	Algorithm Engineering
WS 06/07
PG 503	Xaver: Algorithm Engineering XXL
PG 504	ChemBioSpace Explorer
SS 06
Proseminar	Graphentheorie
PG 478	OGDF: An Open Graph Drawing Framework
WS 05/06
Übung	Algorithm Engineering
Seminar	Netzwerk-Design Algorithmen
PG 478	OGDF: An Open Graph Drawing Framework

SS 05
Übung	Datenstrukturen, Algorithmen und Programmierung 2

WS 04/05
Seminar	Automatisches Zeichnen von Graphen
Proseminar	Algorithmen der Bioinformatik

Diploma and Master Students

11/2010-5/2011: Moritz Schallaböck (New optimal compaction strategies for orthogonal graph layouts) , under joint supervision of Carsten Gutwenger and Karsten Klein. The resulting module will be included in the next OGDF release.

07/2010-2/2011: Sebastian Sondern (Konzeption und Realisierung einer Graphenbibliothek zur Evaluierung von Visualisierungsmethoden für Graphen), under joint supervision of Carsten Gutwenger and Karsten Klein.

06/2010-11/2010: Wolfgang Walz (Multidimensional Scaling Layoutverfahren für die Navigation in chemischen Datenbanken). Multidimensional scaling layout methods for the navigation in chemical databases (and integration in Scaffold Hunter).

06/2009-11/2009: Nils Kriege (Erweiterte Substruktursuche in Moleküldatenbanken und ihre Integration in Scaffoldhunter). Substructure search feature integrated in Scaffold Hunter.

08/2008-02/2009: Gereon Bartel (Coarsening strategies for multi-level graph drawing methods). The resulting Modular Multilevel Mixer will be included in the next release of the Open Graph Drawing Framework (OGDF)

09/2007-02/2008: Philip Thome (Algorithmen zum flächenminimalen planaren Zeichnen von Graphen), under joint supervision of Mike Preuss and Karsten Klein.

04/2007-10/2007: Anne Kunert (Automatic layouts for biological networks), in cooperation with the Molecular Networks in Medical Bioinformatics group at the Max Planck Institut Informatik under joint supervision of Mario Albrecht and Karsten Klein. The resulting layout is implemented in the Cytoscape plugin DomainGraph.

02/2007-08/2007: Mathias Jansen (A branch-and-cut approach for the maximum c-planar subgraph problem). The resulting code will be included in the next release of the Open Graph Drawing Framework (OGDF)

08/2005-02/2006: Bouchta Lakhal (Efficient search in protein databases). Used internally in software at the MPC.

Best watched with Firefox!