Universität Tübingen Fakultät > Wilhelm-Schickard-Institut > Algorithmik > Forschung > Smog - Slog

DFG Project: Neue Modelle und Methoden zum effektiven orthogonalen Layout von Graphen

In this project, we introduce and study new models and methods for effective orthogonal layout of graphs.

A smooth orthogonal drawing of a (planar) graph of maximum degree four is a (planar) drawing, in which each vertex occupies a point on the integer grid and has four available ports, and each edge is a sequence of axis- aligned segments and circular arc segments with common axis-aligned tangents (i.e., quarter, half or three-quarter arc segments).

Intuitively, in a smooth orthogonal drawing we replace the bends in orthogonal drawings by such circular segments while leaving the ports unchanged. Since the readability of orthogonal drawings decreases as the number of bends increases, replacing poly-line edges with smooth curves will result in drawings with improved readability and/or more aesthetic appeal.

All Platonic solids with degree 3 or 4 drawn in the traditional orthogonal style (a-d) with minimum number of bends per edge and redrawn in the smooth orthogonal style (e-f).

A slanted orthogonal drawing of a (non-planar) graph of maximum degree four is a drawing in in which each vertex occupies a point on the integer grid and has four available ports, each edge is drawn as a sequence of horizontal, vertical and diagonal segments, such that a diagonal segment is never incident to a vertex, crossings always involve diagonal segments, and the minimum of the angles formed by two consecutive segments of any edge always is 135 degrees.

Different bend optimal drawings of a non-planar graph in which the crossings are illustrated as gray disks: (a) Orthogonal drawing, (b) Slog drawing, and (c) a variant of Slog, called Sloggy, in which some crossings appear on diagonal segments and some other on rectilinear segments.

In the Slog model, we replace each normal orthogonal bend by two half-bends where each horizontal or vertical segment is followed by a diagonal segment using an angle of 135 degrees. The ports stay the same as before, the great advantage is that we can require that the crossings are only at diagonal segments which makes them clearly visible.

Publications within the project

2017

Patrizio Angelini: Monotone drawings of graphs with few directions Inf. Process. Lett. 120: 16-22 (2017).

Patrizio Angelini, Michael A. Bekos, Giuseppe Liotta, Fabrizio Montecchiani: A Universal Slope Set for 1-Bend Planar Drawings. Symposium on Computational Geometry 2017: 9:1-16.

Michael A. Bekos, Michael Kaufmann, Robert Krug: On the Total Number of Bends for Planar Octilinear Drawings. J. Graph Algorithms Appl. 21(4): 709-730 (2017)

Michael A. Bekos, Henry Förster, Michael Kaufmann: On Smooth Orthogonal and Octilinear Drawings, Graph Drawing 2017, to appear.

2016

Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Giuseppe Di Battista, Peter Eades, Philipp Kindermann, Jan Kratochvíl, Fabian Lipp, Ignaz Rutter: Simultaneous Orthogonal Planarity. Graph Drawing 2016: 532-545

Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Valentino Di Donato, Maurizio Patrignani, Vincenzo Roselli, Ioannis G. Tollis: L-Drawings of Directed Graphs. SOFSEM 2016: 134-147

Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, Ignaz Rutter: Windrose Planarity: Embedding Graphs with Direction-Constrained Edges. SODA 2016: 985-996

2015

Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Robert Krug: Planar Octilinear Drawings with One Bend Per Edge. J. Graph Algorithms Appl. 19(2): 657-680 (2015)

Michael A. Bekos, Michael Kaufmann, Robert Krug: Sloginsky drawings of graphs. IISA 2015: 1-6 (2015)

Michael A. Bekos, Michael Kaufmann, Robert Krug, Martin Siebenhaller: The Effect of Almost-Empty Faces on Planar Kandinsky Drawings. SEA 2015: 352-364 (2015)

2014

Muhammad Jawaherul Alam, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov, Alexander Wolff: Smooth Orthogonal Drawings of Planar Graphs. LATIN 2014: 144-155

Patrizio Angelini, David Eppstein, Fabrizio Frati, Michael Kaufmann, Sylvain Lazard, Tamara Mchedlidze, Monique Teillaud, Alexander Wolff: Universal Point Sets for Planar Graph Drawings with Circular Arcs. J. Graph Algorithms Appl. 18(3): 313-324 (2014)

Michael A. Bekos, Martin Gronemann, Sergey Pupyrev, Chrysanthi N. Raftopoulou: Perfect smooth orthogonal drawings. IISA 2014: 76-81

Michael A. Bekos, Michael Kaufmann, Robert Krug: Sloggy drawings of graphs. IISA 2014: 82-87 (2014)

Michael A. Bekos, Michael Kaufmann, Robert Krug, Thorsten Ludwig, Stefan Näher, Vincenzo Roselli: Slanted Orthogonal Drawings: Model, Algorithms and Evaluations. J. Graph Algorithms Appl. 18(3): 459-489 (2014)

2013

Michael A. Bekos, Michael Kaufmann, Stephen G. Kobourov, Antonios Symvonis: Smooth Orthogonal Layouts. J. Graph Algorithms Appl. 17(5): 575-595 (2013)

Anregungen / Kritik Impressum