Planarization Approaches in Automatic Graph Drawing

Description

Prof. Dr. Michael Jünger; Universität zu Köln
Prof. Dr. Petra Mutzel; Universität Dortmund

 

Project website

 

This automatic graph drawing project concerns the transfer of planarization approaches that have been used primarily in academia so far, to practical applications. We consider a selection of important use-cases, and we try to address the problems arising in these applications. We integrate various application specific constraints into the planarization method, and we provide open source software (see OGDF library) as well as benchmarks instances.


Currently, the application domains include visualization in software engineering and biochemistry, e.g. the visualization of metabolic and protein interaction networks. We will continuously apply the algorithm engineering cycle to our results, so that the engineering process is significantly influenced by the feedback from our cooperation partners.

  
  

Publications

  • M. Chimani, C. Gutwenger, M. Jünger, G. W. Klau, K. Klein and P. Mutzel. "The Open Graph Drawing Framework (OGDF)". R. Tamassia ed. CRC Press. 2012. [More] 
  • C. Buchheim, M. Chimani, C. Gutwenger, M. Jünger and P. Mutzel. "Crossings and Planarization". R. Tamassia ed. CRC Press. 2012. [More] 
  • C. Bachmaier et al.. "The Open Graph Archive: A Community-Driven Effort". Graph Drawing. M. van Kreveld and B. Speckmann eds. 2012. pp. 435-440. [More] 
  • N. Kriege and P. Mutzel. "Subgraph Matching Kernels for Attributed Graphs". International Conference on Machine Learning (ICML). 2012. [More] 
  • M. Chimani, P. Hungerlaender, M. Juenger and P. Mutzel. "An SDP Approach to Multi-level Crossing Minimization", ACM Journal of Experimental Algorithmics. 2012. [More] 
  • M. Chimani, P. Hliněný and P. Mutzel. "Vertex insertion approximates the crossing number of apex graphs", European Journal of Combinatorics, Vol. 33. 2012, pp. 326-335. [More] 
  • K. Klein, N. Kriege and P. Mutzel. "Scaffold Hunter -- Visual Analysis of Chemical Compound Databases". International Conference on Information Visualization Theory and Applications (IVAPP). 2012. [More] 
  • C. Knoll. "Das binäre Stressmodell - Methoden der Nachbearbeitung". Universität zu Köln. 2012. [More] 
  • C. Borchert. "Einbetten und Zeichnen von Bäumen in orthogonale Flächen". Universität zu Köln. 2012. [More] 
  • B. Düppmann. "Vorverarbeitung von Graphen zur Separierung von Kuratowski-Ungleichungen". Universität zu Köln. 2012. [More] 
  • M. Gronemann and M. Jünger. "Drawing Clustered Graphs as Topographic Maps". 2012. [More] 
  • S. D. Kuhnke. "Kompaktierung einer orthogonalen Zeichnung". Universität zu Köln. 2011. [More] 
  • M. Chimani and P. Hliněný. "A Tighter Insertion-based Approximation of the Crossing Number". International Colloquium on Automata, Languages and Programming (ICALP11). 2011. pp. 122-134. [More] 
  • H.-M. Wong. "Upward Planarization and Layout". TU Dortmund. 2011. [More] 
  • C. Demetrescu, M. Kaufmann, S. G. Kobourov and P. Mutzel. "Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191)", Dagstuhl Reports, Vol. 1. 2011, pp. 47-60. [More] 
  • J. J. Fowler, M. Jünger, S. G. Kobourov and M. Schulz. "Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges", Comput. Geom., Vol. 44. 2011, pp. 385-398. [More] 
  • S. Sondern. "Konzeption und Realisierung einer Graphenbibliothek zur Evaluierung von Visualisierungsmethoden für Graphen". Technische Universit{\"a}t Dortmund. 2011. [More] 
  • K. Klein. "Interactive Graph Drawing with Constraints". TU Dortmund. 2011. [More] 
  • K. Klein, N. Kriege and P. Mutzel. "CT-Index: Fingerprint-based graph indexing combining cycles and trees". International Conference on Data Engineering (ICDE). 2011. pp. 1115-1126. [More] 
  • C. Erten et al. "Colored Simultaneous Geometric Embeddings and Universal Pointsets", Algorithmica, Vol. 3. 2011, pp. 569-592. [More] 
  • M. Chimani, P. Hungerländer, M. Jünger and P. Mutzel. "An SDP Approach to Multi-level Crossing Minimization", Workshop on Algorithm Engineering and Experiments 2011 (ALENEX11). 2011. [More] 
  • M. Salehi. "Effiziente Heuristiken zur Extraktion von Kuratowski-Subgraphen". Universität zu Köln. 2011. [More] 
  • S. Mallach. "On separation pairs and split components of biconnected graphs". 2011. [More] 
  • M. Gronemann, M. Jünger, S. Mallach and D. R. Schmidt. "Towards shortest longest edges in orthogonal graph drawing". 2011. [More] 
  • M. Schallaböck. "New Optimal Compaction Strategies for Orthogonal Graph Layout". Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund. 2011. [More] 
  • N. T. Doncheva, K. Klein, F. S. Domingues and M. Albrecht. "Analyzing and visualizing residue networks of protein structures", Trends in Biochemical Sciences, Vol. 36. 2011, pp. 179 - 182. [More] 
  • M. Chimani, C. Gutwenger, P. Mutzel and H.-M. Wong. "Upward Planarization Layout", Journal of Graph Algorithms and Applications, Vol. 15. 2011, pp. 127-155. [More] 
  • C. Gutwenger, K. Klein, P. Mutzel and G. Bartel. "An Experimental Evaluation of Multilevel Layout Methods". Graph Drawing. U. Br, Es and S. Cornelsen eds. 2010. pp. 80-91. [More] 
  • C. Gutwenger. "Application of SPQR-trees in the planarization approach for drawing graphs". Fakultät für Informatik, Technische Universität Dortmund. 2010. [More] 
  • M. Chimani, C. Gutwenger, P. Mutzel, M. Spoenemann and H.-M. Wong. "Crossing Minimization and Layouts of Directed Hypergraphs with Port Constraints". Graph Drawing. 2010. [More] 
  • M. Chimani, C. Gutwenger, P. Mutzel and H.-M. Wong. "Layer-free upward crossing minimization", J. Exp. Algorithmics, Vol. 15. 2010, pp. 2.1-2.27. [More] 
  • M. Gronemann. "Engineering the Fast-Multipole-Multilevel Method for multicore and SIMD architectures". Lehrstuhl für Algorithm Engineering, Fakultät für Informatik, Technische Universität Dortmund. 2009. [More] 
  • A. Kerren et al.. "On Open Problems in Biological Network Visualization". Graph Drawing. 2009. pp. 256-267. [More] 
  • P. Mutzel. "Optimization in Leveled Graphs". Floudas, C. A., Pardalos and P. M. eds. Springer. 2009. pp. 2813-2820. [More] 
  • C. Gutwenger, S.-H. Hong, P. Mutzel and P. Eades. "Graph Drawing Algorithms". M. Atallah and M. Blanton eds. Chapman and Hall. 2009. pp. 6-1-6-28. [More] 
  • P. Mutzel. "The Crossing Number of Graphs: Theory and Computation". Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. S. Albers, H. Alt and S. Näher eds. 2009. pp. 305-317. [More] 
  • M. Jünger and M. Schulz. "Intersection graphs in simultaneous embedding with fixed edges". Universität zu Köln. 2009. [More] 
  • C. Gutwenger, M. Jünger, P. Mutzel, M. Schulz and J. J. Fowler. "An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges". 2009. pp. 157-168. [More] 
  • M. Chimani, P. Hliněný and P. Mutzel. "Approximating the Crossing Number of Apex Graphs". Graph Drawing. 2009. pp. 432-434. [More] 
  • M. Chimani, C. Gutwenger, P. Mutzel and C. Wolf. "Inserting a vertex into a planar graph". SODA '09: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. 2009. pp. 375-383. [More] 
  • K. Klein, N. Kriege, P. Mutzel, H. Waldmann and S. Wetzel. "Scaffold Hunter - Interactive Exploration of Chemical Space". Graph Drawing. 2009. pp. 426-427. [More] 
  • S. Wetzel et al. "Interactive exploration of chemical space with Scaffold Hunter", Nat Chem Biol, Vol. 5, 08, 2009, pp. 581-583. [More] 
  • M. Chimani, C. Gutwenger, P. Mutzel and H.-M. Wong. "Upward Planarization Layout". Graph Drawing. 2009. pp. 94-106. [More] 
  • M. Schulz. "Simultaneous Graph Drawing". Universität zu Köln. 2008. [More] 
  • M. Chimani. "Exact Crossing Minimization". Technische Universität Dortmund. 2008. [More] 
  • M. Albrecht et al.. "A graph-drawing perspective to some open problems in molecular biology". Technische Universität Dortmund. 2008. [More] 
  • B. T. Zey. "Algorithms for Planar Graph Augmentation". 2008. [More] 
  • S. Mallach. "Beschleunigung ausgewählter paralleler Standard Template Library Algorithmen". 2008. [More] 
  • C. Wolf. "Inserting a vertex into a planar graph". 2008. [More] 
  • M. Baum. "Quasi-Orthogonales Zeichnen von Cluster-Graphen mit Kantenbündelungen". 2008. [More] 
  • G. Bartel. "Zerlegungsstrategien für Multilevel-Graphdrawing-Verfahren". 2008. [More] 
  • D. Emig, K. Klein, A. Kunert, P. Mutzel and M. Albrecht. "Visualizing Domain Interaction Networks and the Impact of Alternative Splicing Events". MEDIVIS '08: Proceedings of the 2008 Fifth International Conference BioMedical? Visualization: Information Visualization in Medical and Biomedical Informatics. 2008. pp. 36-43. [More] 
  • M. Chimani, P. Mutzel and I. M. Bomze. "A New Approach to Exact Crossing Minimization". ESA. 2008. pp. 284-296. [More] 
  • M. Chimani, M. Jünger and M. Schulz. "Crossing Minimization meets Simultaneous Drawing". PacificVis. 2008. pp. 33-40. [More] 
  • C. Buchheim et al. "A branch-and-cut approach to the crossing number problem", Discrete Optimization, Vol. 5. 2008, pp. 373-388. [More] 
  • D. Emig et al. "Integrative Visual Analysis of the Effects of AlternativeSplicing on Protein Domain Interaction Networks", J. Integrative Bioinformatics, Vol. 5. 2008. [More] 
  • M. Chimani, C. Gutwenger, M. Jansen, K. Klein and P. Mutzel. "Computing Maximum C-Planar Subgraphs". Graph Drawing. 2008. pp. 114-120. [More] 
  • S. P. Borgatti, S. G. Kobourov, O. Kohlbacher and P. Mutzel. "Dagstuhl Seminar 08191: Graph Drawing". 2008. [More] 
  • M. Chimani, C. Gutwenger, P. Mutzel and H.-M. Wong. "Layer-Free Upward Crossing Minimization". WEA. 2008. pp. 55-68. [More] 
  • A. Estrella-Balderrama, E. Gassner, M. Jünger, M. Percan, M. Schaefer and M. Schulz. "Simultaneous geometric graph embeddings". GD'07: Proceedings of the 15th international conference on Graph drawing. 2008. pp. 280-290. [More] 
  • M. Jünger, S. G. Kobourov, M. Schulz and J. J. Fowler. "Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges". WG. 2008. pp. 146-158. [More] 
  • M. Jünger, S. G. Kobourov, M. Schulz and J. J. Fowler. "Characterizing Simultaneous Embedding with Fixed Edges", Electronic Notes in Discrete Mathematics, Vol. 31. 2008, pp. 41-44. [More] 
  • C. Gutwenger, K. Klein and P. Mutzel. "Planarity Testing and Optimal Edge Insertion with Embedding Constraints", J. Graph Algorithms Appl., Vol. 12. 2008, pp. 73-95. [More] 
  • P. Mutzel. "Recent Advances in Exact Crossing Minimization (Extended Abstract)", Electronic Notes in Discrete Mathematics, Vol. 31. 2008, pp. 33-36. [More] 
  • G. Italiano, P. Mutzel, P. Sanders and M. Skutella. "Proc. Intern. Oberwolfach Workshop on Algorithm Engineering Oberwolfach Report No. 25/2007". 2007. [More] 
  • M. Percan. "Constrained Planarity and Augmentation Problems". Universität zu Köln. 2007. [More] 
  • T. Kerkhof. "Algorithmen zur Bestimmung von guten Graph-Einbettungen für orthogonale Zeichnungen". 2007. [More] 
  • M. Bachra. "Geradliniges Zeichnen von Cluster-Graphen im Divide-and-Conquer-Ansatz". 2007. [More] 
  • M. Jansen. "Ein Branch-and-Cut Ansatz für das Maximum C-planare Subgraphen Problem". 2007. [More] 
  • A. Kunert. "Layoutverfahren für biologische Netzwerke". 2007. [More] 
  • S. Wetzel, K. Klein, A. Schuffenhauer, P. Ertl, P. Mutzel and H. Waldmann. "Software-assisted scaffold tree analysis of large compound collections". 2007. [More] 
  • M. Chimani and C. Gutwenger. "Algorithms for the Hypergraph and the Minor Crossing NumberProblems". ISAAC. 2007. pp. 184-195. [More] 
  • U. Brandes et al.. "Colored Simultaneous Geometric Embeddings". COCOON. 2007. pp. 254-263. [More] 
  • D. Emig et al.. "Integration and visualization of exon expression data with domain interaction networks". [More] 
View less
  

Projects

[ Back ]