Slanted Orthogonal Drawings

Bekos, Michael A. and Kaufmann, Michael and Krug, Robert and Näher, Stefan and Roselli, Vincenzo (2013) Slanted Orthogonal Drawings. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 424-435 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_37).

Full text not available from this repository.

Abstract

We introduce a new model that we call slanted orthogonal graph drawing. While in traditional orthogonal drawings each edge is made of axis-aligned line-segments, in slanted orthogonal drawings intermediate diagonal segments on the edges are also permitted, which allows for: (a) smoothening the bends of the produced drawing (as they are replaced by pairs of “half-bends”), and, (b) emphasizing the crossings of the drawing (as they always appear at the intersection of two diagonal segments). We present an approach to compute bend-optimal slanted orthogonal representations, an efficient heuristic to compute close-to-optimal drawings in terms of the total number of bends using quadratic area, and a corresponding LP formulation, when insisting on bend optimality. On the negative side, we show that bend-optimal slanted orthogonal drawings may require exponential area.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
ID Code:1394

Repository Staff Only: item control page

References

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 24–35. Springer, Heidelberg (1994)

Cornelsen, S., Karrenbauer, A.: Accelerated bend minimization. Journal of Graph Algorithms Applications 16(3), 635–650 (2012)

Fößmeier, U., Heß, C., Kaufmann, M.: On improving orthogonal drawings: The 4M-algorithm. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 125–137. Springer, Heidelberg (1999)

Fößmeier, U., Kaufmann, M.: Drawing high degree graphs with low bend numbers. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 254–266. Springer, Heidelberg (1996)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM Journal of Computing 31(2), 601–625 (2001)

Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: 21st Symposium on Foundations of Computer Science, vol. 1547, pp. 270–281. IEEE (1980)

Nöllenburg, M., Wolff, A.: Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Trans. Vis. Comput. Graph. 17(5), 626–641 (2011)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM Journal of Computing 16(3), 421–444 (1987)

Tamassia, R., Tollis, I.G.: Planar grid embedding in linear time. IEEE Transactions on Circuits and Systems 36(9), 1230–1234 (1989)

Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Transaction on Computers 30(2), 135–140 (1981)