On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and Kandinsky Drawings

Bekos, Michael A. and Förster, Henry and Kaufmann, Michael (2017) On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and Kandinsky Drawings. In: Graph Drawing and Network Visualization, GD 2017, September 25-27 , pp. 169-183(Official URL: https://doi.org/10.1007/978-3-319-73915-1_15).

Full text not available from this repository.

Abstract

We study two variants of the well-known orthogonal drawing model: (i) the smooth orthogonal, and (ii) the octilinear. Both models form an extension of the orthogonal, by supporting one additional type of edge segments (circular arcs and diagonal segments, respectively). For planar graphs of max-degree 4, we analyze relationships between the graph classes that can be drawn bendless in the two models and we also prove NP-hardness for a restricted version of the bendless drawing problem for both models. For planar graphs of higher degree, we present an algorithm that produces bi-monotone smooth orthogonal drawings with at most two segments per edge, which also guarantees a linear number of edges with exactly one segment.

Item Type: Conference Paper
Classifications: P Styles > P.120 Circular
P Styles > P.300 Curved
P Styles > P.600 Poly-line
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1602

Actions (login required)

View Item View Item