TU Dortmund
Fakultät Informatik
Lehrstuhl für Algorithm Engineering

Planarisierungsverfahren im Automatischen Zeichnen von Graphen

im Rahmen des DFG-SPP 1307

Start

Beteiligte

Publikationen

Open Graph Drawing Framework OGDF

Simultaneous Graph Drawing Tool SGDT

Links

Journal Articles

An SDP Approach to Multi-level Crossing Minimization
Markus Chimani, Philipp Hungerlaender, Michael Juenger, and Petra Mutzel
ACM Journal of Experimental Algorithmics, to appear 2012.

Vertex insertion approximates the crossing number for apex graphs
M. Chimani, P. Hlineny, and P. Mutzel
in: European Journal of Combinatorics, Vol. 33, pp. 326-335, 2012,
Special Issue on Topological and Geometric Graph Theory.

Analyzing and visualizing residue networks of protein structures
Nadezhda T. Doncheva, Karsten Klein, Francisco S. Domingues, and Mario Albrecht
Trends in Biochemical Sciences 2011.

Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges
J. Joseph Fowler, Michael Jünger, Stephen G. Kobourov, and Michael Schulz
Comput. Geom. 44(8): 385-398 (2011)

Colored Simultaneous Geometric Embeddings and Universal Pointsets
Ulrik Brandes, Cesim Erten, Alejandro Estrella-Balderrama, J. Joseph Fowler, Fabrizio Frati, Markus Geyer, Carsten Gutwenger, Seok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, Giuseppe Liotta, Petra Mutzel, and Antonios Symvonis
Algorithmica 60(3), 2011, 569-592.

Upward planarization layout
M. Chimani, C. Gutwenger, P. Mutzel, and H.-M. Wong
in: Journal of Graph Algorithms and Applications, 15(1):127-155, 2011

Layer-Free Upward Crossing Minimization
Markus Chimani , Carsten Gutwenger, Petra Mutzel, and Hoi-Ming Wong
in: ACM Journal of Experimental Algorithmics, volume 15, 2010

Interactive exploration of chemical space with scaffold hunter
S. Wetzel, K. Klein, S. Renner, D. Rauh, T. I. Oprea, P. Mutzel, and H. Waldmann
in: Nature Chemical Biology, 5(8):581-583, August 2009

A branch-and-cut approach to the crossing number problem
C. Buchheim, M. Chimani, D. Ebner, C. Gutwenger, M. Jünger, G.W. Klau, P. Mutzel, and R. Weiskircher
in: E. Balas, A. Hoffman, and T. McCormick (eds.)
Special issue dedicated to the memory of George B. Dantzig. Discrete Optimization, 5:373-388, 2008.

Integrative visual analysis of the effects of alternative splicing on protein domain interaction networks
D. Emig, M. S. Cline, K. Klein, A. Kunert, P. Mutzel, T. Lengauer, and M. Albrecht
in: J. Integrative Bioinformatics, 5(2:101):1-15, 2008.

Characterizing simultaneous embedding with fixed edges
J. J. Fowler, M. Jünger, S. G. Kobourov, and M. Schulz
in: Topological and Geometric Graph Theory '08, volume 31 of Electronic Notes in Discrete Mathematics, pages 41-44, 2008.

Planarity testing and optimal edge insertion with embedding constraints
C. Gutwenger, K. Klein, and P. Mutzel
in: Journal of Graph Algorithms and Applications, 12(1):73-95, 2008.

Recent advances in exact crossing minimization (extended abstract)
P. Mutzel
in: Electronic Notes in Discrete Mathematics, 31:31-36, 2007.


Articles in Refereed Conference Proceedings

Subgraph Matching Kernels for Attributed Graphs
Nils Kriege and Petra Mutzel
International Conference on Machine Learning (ICML) 2012, to appear.

Scaffold Hunter - Visual Analysis of Chemical Compound Databases
Karsten Klein, Nils Kriege, and Petra Mutzel
International Conference on Information Visualization Theory and Applications (IVAPP) 2012, Best Paper Award, to appear.

The Open Graph Archive: A Community-Driven Effort
Christian Bachmaier, Franz-Josef Brandenburg, Philip Effinger, Carsten Gutwenger, Jyrki Katajainen, Karsten Klein, Miro Spönemann, Matthias Stegmaier, and Michael Wybrow
Graph Drawing 2011: 435-440

CT-Index: Fingerprint-based graph indexing combining cycles and trees
K. Klein, N. Kriege, and P. Mutzel
in: Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, Hannover, Germany, 2011, 1115-1126

A tighter insertion-based approximation of the crossing number
M. Chimani and P. Hlineny
International Colloquium on Automata, Languages and Programming (ICALP11), LNCS 6755, pp. 122-134, Springer, 2011.

An SDP approach to multilevel crossing minimization
M. Chimani, P. Hungerländer, M. Jünger, and P. Mutzel
Workshop on Algorithm Engineering and Experiments 2011 (ALENEX11).

Crossing Minimization and Layouts of Directed Hypergraphs with Port Constraints
Markus Chimani, Carsten Gutwenger, Petra Mutzel, Miro Spönemann, and Hoi-Ming Wong
in: Ulrik Brandes and Sabine Cornelsen (ed.), Graph Drawing 2010
Lecture Notes in Computer Science, pages 141-152, Springer-Verlag 2010.

An experimental evaluation of multilevel layout methods
G. Bartel, C. Gutwenger, K. Klein, and P. Mutzel
in: Ulrik Brandes and Sabine Cornelsen (ed.), Graph Drawing 2010
Lecture Notes in Computer Science, pages 80-91, Springer Verlag 2010.

Colored simultaneous geometric embeddings and universal pointsets
U. Brandes, C. Erten, A. Estrella-Balderrama, J. J. Fowler, F. Frati, M. Geyer, C. Gutwenger,
S.-H. Hong, M. Kaufmann, S. G. Kobourov, G. Liotta, P. Mutzel, and A. Symvonis
in: Ulrik Brandes and Sabine Cornelsen (ed.), Graph Drawing 2010

On open problems in biological network visualization
M. Albrecht, A. Kerren, K. Klein, O. Kohlbacher, P. Mutzel, W. Paul, F. Schreiber, and M. Wybrow
in: D. Eppstein and E. R. Gansner (ed.), Graph Drawing 2009
Lecture Notes in Computer Science, pages 256-267, Springer-Verlag 2009.

Scaffold hunter - interactive exploration of chemical space (poster)
K. Klein, N. Kriege, P. Mutzel, H. Waldmann, and S. Wetzel
in: D. Eppstein and E. R. Gansner (ed.), Graph Drawing 2009
Lecture Notes in Computer Science, pages 426-427, Springer-Verlag 2009.

Upward Planarization Layout
Markus Chimani, Carsten Gutwenger, Petra Mutzel, and Hoi-Ming Wong
in: D. Eppstein, E. Gansner (eds.), 17th Symposium on Graph Drawing 2009, Chicago
Lecture Notes in Computer Science 5849, pages 94-106, Springer-Verlag 2009.

Port Constraints in Hierarchical Layout of Data Flow Diagrams
M. Spönemann, H. Fuhrmann, R. von Hanxleden, and P. Mutzel
in: D. Eppstein, E. Gansner (eds.), 17th Symposium on Graph Drawing 2009, Chicago
Lecture Notes in Computer Science 5849, pages 135-146, Springer-Verlag 2009.

Inserting a vertex into a planar graph
M. Chimani, C. Gutwenger, P. Mutzel, and C. Wolf
in: C. Mathieu, editor, SODA, pages 375-383. SIAM, 2009.

Approximating the crossing number of apex graphs (poster)
M. Chimani, P. Hlineny, and P. Mutzel
in: Y. Tollis (ed.), editor, Graph Drawing (GD 08), volume 5417 of Lecture Notes in Computer Science, pages 432-434. Springer-Verlag, 2009.

An SPQR-approach to decide special cases of simultaneous embedding with fixed edges
J. J. Fowler, C. Gutwenger, M. Jünger, P. Mutzel, and M. Schulz
in: Graph Drawing '08, volume 5417 of Lecture Notes in Computer Science, pages 157-168, 2009.

Computing maximum c-planar subgraphs
M. Chimani, C. Gutwenger, M. Jansen, K. Klein, and P. Mutzel
in: 16th International Symposiumon Graph Drawing (GD 2008), pages 114-120. Springer, 2009.

Dagstuhl Seminar 08191: Graph Drawing
S.P. Borgatti, S. Kobourov, O. Kohlbacher, and P. Mutzel, editors
in: Dagstuhl Seminar 08191: Graph Drawing, Wadern, 2008. Schlo&szl;ig Dagstuhl.

Layer-free upward crossing minimization
M. Chimani, C. Gutwenger, P. Mutzel, and H.-M. Wong
in: WEA 2008: Workshop on Experimental Algorithms, volume 5038 of LNCS, pages 55-68. Springer, 2008.

Crossing minimization meets simultaneous drawing
M. Chimani, M. Jünger, and M. Schulz
in: I. Fujishiro, H. Li, and K.-L. Ma, editors, IEEE Pacic Visualization Symposium 2008,IEEE vgtc, pages 33-40, 2008.

A new approach to exact crossing minimization
M. Chimani, P. Mutzel, and I. Bomze
in: 16th Annual European Symposium on Algorithms (ESA08), number 5193 in LNCS, pages 284-296. Springer, 2008.

Integration and visualization of exon expression data with domain interaction networks (poster)
D. Emig, M. S. Cline, K. Klein, A. Kunert, P. Mutzel, T. Lengauer, and M. Albrecht
in: BioMed Conference on Targeting and Tinkering with Interaction Networks.

Visualizing domain interaction networks and the impact of alternative splicing events
D. Emig, M. S. Cline, K. Klein, A. Kunert, P. Mutzel, T. Lengauer, and M. Albrecht
in: Proc. 12th Internat. Conf. on BioMedical Visualization (MediVis): Information Visualization in Medical and Biomedical Informatics,
pages 36-43, London, United Kingdom, 2008. IEEE Computer Society.

Simultaneous geometric graph embeddings
A. Estrella-Balderrama, E. Gassner, M. Jünger, M. Percan, M. Schaefer, and M. Schulz
in: S.-H. Hong, T. Nishizeki, and W. Quan, editors, Graph Drawing '07, volume 4875 of Lecture Notes in Computer Science, pages 280-290, 2008.

Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges
J. J. Fowler, M. Jünger, S. G. Kobourov, and M. Schulz
in: H. Broersma, T. Erlebach, T. Friedetzky, and D. Paulusma, editors, Workshop on Graph-Theoretical Concepts in Computer Science '08, volume 5344 of Lecture Notes in Computer Science, pages 146-158, 2008.

Scaffold hunter: Exploiting holes in chemical space (poster)
S. Wetzel, K. Klein, A. Schuffenhauer, P. Ertl, P. Mutzel, and H. Waldmann
in: In 8th International Conference on Chemical Structures (ICCS 2008), 2008.

Proc. Intern. Oberwolfach Workshop on Algorithm Engineering, volume 25 of Oberwolfach Report. Mathematisches Forschungsinstitut Oberwolfach, 2007.
G.F. Italiano, P. Mutzel, P. Sanders, and M. Skutella, editors

Algorithms for the hypergraph and the minor crossing number problems
M. Chimani and C. Gutwenger
in: 18th Annual International Symposium on Algorithms and Computation (ISAAC'07), volume 4835 of Lecture Notes in Computer Science, pages 184-195, 2007.

Biochemistree: software-assisted scaffold tree analysis of large compound collections (poster)
S.Wetzel, K. Klein, A. Schuffenhauer, P. Ertl, P. Mutzel, and H.Waldmann
in: 4th Joint Sheffield Conference on Chemoinformatics, Sheffield, England, 2007.

Colored simultaneous geometric embeddings
U. Brandes, C. Erten, J. J. Fowler, F. Frati, M. Geyer, C. Gutwenger, S.-H. Hong, M. Kaufmann,
S. G. Kobourov, G. Liotta, P. Mutzel, and A. Symvonis
in: 13th International Computing and Combinatorics Conference, volume 4598 of Lecture Notes in Computer Science, pages 254-263, 2007.


Technical Reports

Drawing Clustered Graphs as Topographic Maps
Martin Gronemann and Michael Jünger
in: Technical Report, Universität zu Köln, 2012.

On separation pairs and split components of biconnected graphs
Sven Mallach
in: Technical Report, Universität zu Köln, 2011.

Towards shortest longest edges in orthogonal graph drawing
Martin Gronemann, Michael Jünger, Sven Mallach and Daniel R. Schmidt
in: Technical Report, Universität zu Köln, 2011.

Intersection graphs in simultaneous embedding with fixed edges
M. Jünger and M. Schulz
in: Technical Report, Universität zu Köln, 2009.

A graph-drawing perspective to some open problems in molecular biology
M. Albrecht, A. Kerren, K. Klein, O. Kohlbacher, P. Mutzel, W. Paul, F. Schreiber, and M. Wybrow.
in: Technical Report TR08-01-003, Lehrstuhl XI für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, Juni 2008.


PhD Theses

Upward Planarization and Layout
Hoi-Ming Wong
in: PhD thesis, Fakultät für Informatik, Technische Universität Dortmund, 2011.

Interactive Graph Drawing with Constraints
K. Klein
in: PhD thesis, Fakultät für Informatik, Technische Universität Dortmund, 2011.

Application of SPQR-trees in the planarization approach for drawing graphs
C. Gutwenger
in: PhD thesis, Fakultät für Informatik, Technische Universität Dortmund, 2010.

Exact Crossing Minimization
M. Chimani
in: PhD thesis, Fakultät für Informatik, Technische Universität Dortmund, 2008.

Simultaneous Graph Drawing
M. Schulz
in: PhD thesis, Universität zu Köln, 2008.

Constrained Planarity and Augmentation Problems
M. Percan
in: PhD thesis, Universität zu Köln, 2007.


Bachelor/Master/Diploma Theses

Das binäre Stressmodell - Methoden der Nachbearbeitung
Christian Knoll
in: Diplomarbeit, Universität zu Köln, 2012.

Einbetten und Zeichnen von Bäumen in orthogonale Flächen
Christian Borchert
in: Diplomarbeit, Universität zu Köln, 2012.

Vorverarbeitung von Graphen zur Separierung von Kuratowski-Ungleichungen
Bernd Düppmann
in: Diplomarbeit, Universität zu Köln, 2012.

Effiziente Heuristiken zur Extraktion von Kuratowski-Subgraphen
Massud Salehi
in: Diplomarbeit, Universität zu Köln, 2011.

Kompaktierung einer orthogonalen Zeichnung
Sascha D. Kuhnke
in: Bachelorarbeit, Universität zu Köln, 2011.

New Optimal Compaction Strategies for Orthogonal Graph Layout
Moritz Schallaböck
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät fär Informatik, Technische Universitüt Dortmund, 2011.

Konzeption und Realisierung einer Graphenbibliothek zur Evaluierung von Visualisierungsmethoden für Graphen
S. Sondern
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät fär Informatik, Technische Universitüt Dortmund, 2011.

Engineering the Fast-Multipole-Multilevel Method for multicore and SIMD architectures
M. Gronemann
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2009.

Zerlegungsstrategien für Multilevel-Graphdrawing-Verfahren
G. Bartel
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2008.

Quasi-Orthogonales Zeichnen von Cluster-Graphen mit Kantenbündelungen
M. Baum
in: Diplomarbeit, Universität zu Köln, 2008.

Beschleunigung ausgewählter paralleler Standard Template Library Algorithmen
S. Mallach
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2008.

Inserting a vertex into a planar graph
C. Wolf
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2008.

Algorithms for Planar Graph Augmentation
B. T. Zey
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2008.

Ein Branch-and-Cut Ansatz für das Maximum C-planare Subgraphen Problem
M. Jansen
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2007.

Algorithmen zur Bestimmung von guten Graph-Einbettungen für orthogonale Zeichnungen
T. Kerkhof
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2007.

Layoutverfahren für biologische Netzwerke
A. Kunert
in: Diplomarbeit, Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund, 2007.

Geradliniges Zeichnen von Cluster-Graphen im Divide-and-Conquer-Ansatz
M. Bachran
in: Diplomarbeit, Universität zu Köln, 2007.


Sonstige Publikationen

Crossings and Planarization
Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel
Chapter 2 in: R. Tamassia (ed.), Handbook of Graph Drawing and Visualization
CRC Press, to appear in 2012

The Open Graph Drawing Framework (OGDF)
Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel
Chapter 15 in: R. Tamassia (ed.), Handbook of Graph Drawing and Visualization
CRC Press, to appear in 2012

Dagstuhl Seminar 11191: Graph Drawing with Algorithm Engineering Methods
Camil Demetrescu, Michael Kaufmann, Stephen G. Kobourov, and Petra Mutzel
Dagstuhl Reports 1(5): 47-60 (2011)

Graph drawing algorithms
P. Eades, C. Gutwenger, S. Hong, and P. Mutzel.
in: Algorithms and Theory of Computation Handbook, volume 2 of CRC Applied Algorithms and Data Structures series, chapter 6, pages 6-1-6-28. Chapman and Hall 2009, Second Edition.

The crossing number of graphs: Theory and computation
P. Mutzel.
in: S. Albers, H. Alt, and S. Näher (editors), Efficient Algorithms,
Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, volume 5760 of Lecture Notes in Computer Science, pages 305-317, Springer 2009.

Optimization in leveled graphs
P. Mutzel.
in: C.A. Floudas and P.M. Pardalos (editors), Encyclopedia of Optimization, pages 2813-2820, Springer 2009, Second Edition.


Software

Scaffold Hunter (2010)
Link: Scaffold Hunter

SGDT - Simultaneous Graph Drawing Tool (2008)
T. Dehling,M. Jünger,M. Schulz, and W. Zychowicz
Link: SGDT

OGDF: An Open Graph Drawing Framework
Link: ODGF