Universität Tübingen  Fakultät > WilhelmSchickardInstitut > Algorithmik > Forschung > Smog  Slog 

DFG Project: Neue Modelle und Methoden zum effektiven orthogonalen Layout von GraphenIn 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 axisaligned tangents (i.e., quarter, half or threequarter 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 polyline 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 (ad)
with minimum number of bends per edge and redrawn in the smooth orthogonal style (ef).
A slanted orthogonal drawing of a (nonplanar) 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 nonplanar 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 halfbends 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: 1622 (2017). Patrizio Angelini, Michael A. Bekos, Giuseppe Liotta, Fabrizio Montecchiani: A Universal Slope Set for 1Bend Planar Drawings. Symposium on Computational Geometry 2017: 9:116. Michael A. Bekos, Michael Kaufmann, Robert Krug: On the Total Number of Bends for Planar Octilinear Drawings. J. Graph Algorithms Appl. 21(4): 709730 (2017) Michael A. Bekos, Henry Förster, Michael Kaufmann: On Smooth Orthogonal and Octilinear Drawings, Graph Drawing 2017, to appear. 2016Patrizio 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: 532545 Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Valentino Di Donato, Maurizio Patrignani, Vincenzo Roselli, Ioannis G. Tollis: LDrawings of Directed Graphs. SOFSEM 2016: 134147 Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, Ignaz Rutter: Windrose Planarity: Embedding Graphs with DirectionConstrained Edges. SODA 2016: 985996 2015Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Robert Krug: Planar Octilinear Drawings with One Bend Per Edge. J. Graph Algorithms Appl. 19(2): 657680 (2015) Michael A. Bekos, Michael Kaufmann, Robert Krug: Sloginsky drawings of graphs. IISA 2015: 16 (2015) Michael A. Bekos, Michael Kaufmann, Robert Krug, Martin Siebenhaller: The Effect of AlmostEmpty Faces on Planar Kandinsky Drawings. SEA 2015: 352364 (2015) 2014Muhammad Jawaherul Alam, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov, Alexander Wolff: Smooth Orthogonal Drawings of Planar Graphs. LATIN 2014: 144155 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): 313324 (2014) Michael A. Bekos, Martin Gronemann, Sergey Pupyrev, Chrysanthi N. Raftopoulou: Perfect smooth orthogonal drawings. IISA 2014: 7681 Michael A. Bekos, Michael Kaufmann, Robert Krug: Sloggy drawings of graphs. IISA 2014: 8287 (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): 459489 (2014) 2013Michael A. Bekos, Michael Kaufmann, Stephen G. Kobourov, Antonios Symvonis: Smooth Orthogonal Layouts. J. Graph Algorithms Appl. 17(5): 575595 (2013) 
Anregungen / Kritik Impressum 