Abstract
We study the problem of creating smooth orthogonal layouts for planar graphs. While in traditional orthogonal layouts every edge is made of a sequence of axis-aligned line segments, in smooth orthogonal layouts every edge is made of axis-aligned segments and circular arcs with common tangents. Our goal is to create such layouts with low edge complexity, measured by the number of line and circular arc segments. We show that every biconnected 4-planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity-2 traditional orthogonal layout, we can transform it into a smooth complexity-2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity-2 layout.
The work of M.A. Bekos is implemented within the framework of the Action “Supporting Postdoctoral Researchers” of the Operational Program “Education and Lifelong Learning” (Action’s Beneficiary: General Secretariat for Research and Technology), and is co-financed by the European Social Fund (ESF) and the Greek State. The work of S. G. Kobourov is supported in part by NSF grant CCF-1115971 and a grant from the Humboldt Foundation.
Chapter PDF
Similar content being viewed by others
References
Biedl, T., 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)
Biedl, T.C., Kaufmann, M.: Area-Efficient Static and Incremental Graph Drawings. In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol. 1284, pp. 37–52. Springer, Heidelberg (1997)
Brandes, U., Schlieper, B.: Angle and Distance Constraints on Tree Drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 54–65. Springer, Heidelberg (2007)
Brandes, U., Wagner, D.: Using graph layout to visualize train interconnection data. J. of Graph Algorithms and Applications 4(3), 135–155 (2000)
Chan, T.M.: Geometric applications of a randomized optimization technique. Discrete Computational Geometry 22(4), 547–567 (1999)
Cheng, C.C., Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Drawing planar graphs with circular arcs. Discrete Comput. Geom. 25(3), 405–418 (2001)
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Löffler, M.: Planar and Poly-arc Lombardi Drawings. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 308–319. Springer, Heidelberg (2012)
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi Drawings of Graphs. J. of Graph Algorithms and Applications 16(1), 85–108 (2011)
Finkel, B., Tamassia, R.: Curvilinear Graph Drawing Using the Force-Directed Method. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 448–453. Springer, Heidelberg (2005)
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. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 286–297. Springer, Heidelberg (1995)
Goodrich, M.T., Wagner, C.G.: A framework for drawing planar graphs with curves and polylines. J. of Algorithms 37(2), 399–421 (2000)
Holten, D., van Wijk, J.J.: Force-directed edge bundling for graph visualization. Computer Graphics Forum 28(3), 983–990 (2009)
Huang, W., Eades, P., Hong, S.H.: A graph reading behavior: Geodesic-path tendency. In: IEEE Pacific Visualization Symp. (PacificVis 2009), pp. 137–144. IEEE (2009)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)
Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. of Graph Algorithms Applications 6(1), 115–129 (2002)
Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: 21st Annual IEEE Symp. on Foundations of Computer Science, vol. 1547, pp. 270–281. IEEE (1980)
Lombardi, M., Hobbs, R.: Mark Lombardi: Global Networks. Independent Curators (2003)
Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. of Computing 16(3), 421–444 (1987)
Tamassia, R., Tollis, I.: 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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bekos, M.A., Kaufmann, M., Kobourov, S.G., Symvonis, A. (2013). Smooth Orthogonal Layouts. In: Didimo, W., Patrignani, M. (eds) Graph Drawing. GD 2012. Lecture Notes in Computer Science, vol 7704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36763-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-36763-2_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36762-5
Online ISBN: 978-3-642-36763-2
eBook Packages: Computer ScienceComputer Science (R0)