Compact Graph Drawing with Port Constraints

• Applicants: Professor Dr. Reinhard von Hanxleden; Professorin Dr. Petra Mutzel
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 250885464

• Final Report Year: 2018

Final Report Abstract

The goal of this project was to design new algorithms for drawing graphs, with the special focus on compactness and port constraints. Our compactness goal was to minimize the area of the smallest bounding box around the drawing while achieving an ideal aspect ratio. We have suggested new models and methods for the layered drawing method as well as for the planarization-based orthogonal compaction method. Our new methods have been integrated into KIELER, as part of the Eclipse Layout Kernel (ELK), and into OGDF. They are thus usable in a number of academic and commercial modeling environments based on these frameworks, such as UC Berkeley’s Ptolemy project or the EHANDBOOK from Bosch/ETAS. For the empirical evaluation we have used classical benchmark sets used in graph drawing as well as data flow diagrams used in the area of embedded systems. Our contributions could directly be employed in industrial applications, since automatic graph layout is now increasingly becoming a very relevant functionality for the model-based design process of embedded systems.

Publications

• “Compact Layered Drawings of General Directed Graphs”. In: Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD ’16). Ed. by Yifan Hu and Martin Nöllenburg. Vol. 9801. Lecture Notes in Computer Science. Springer, 2016, pp. 209–221
  Jabrayilov, Adalat; Mallach, Sven; Mutzel, Petra; Rüegg, Ulf & von Hanxleden, Reinhard
  
• “Using One-Dimensional Compaction for Smaller Graph Drawings”. In: Proceedings of the 9th International Conference on the Theory and Application of Diagrams (DIAGRAMS ’16). Vol. 9781. LNCS. Springer, 2016, pp. 212–218
  Rüegg, Ulf; Schulze, Christoph Daniel; Grevismühl, Daniel & von Hanxleden, Reinhard
  
• “Generalized Layerings for Arbitrary and Fixed Drawing Areas”. In: Journal of Graph Algorithms and Applications 21.5 (2017), pp. 823–856
  Rüegg, Ulf; Ehlers, Thorsten; Spönemann, Miro & Von Hanxleden, Reinhard
  
• “More Compact Orthogonal Drawings by Allowing Additional Bends”. In: Information – Open Access Journal of Information Science 9.7 (2018), 1–24 (153)
  Jünger, Michael; Mutzel, Petra & Spisla, Christiane
  
• “Orthogonal Compaction using Additional Bends”. In: Proceedings of the 13th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2018). Ed. by Alexandru Telea, Andreas Kerren, and José Braz. SciTePress, 2018, pp. 144–155
  Jünger, Michael; Mutzel, Petra & Spisla, Christiane
  
• “Wrapping Layered Graphs”. In: Proceedings of the 10th International Conference on the Theory and Application of Diagrams (DIAGRAMS ’18). Springer, 2018, pp. 743–747
  Rüegg, Ulf & von Hanxleden, Reinhard