Abstract
An octilinear drawing of a planar graph is one in which each edge is drawn as a sequence of horizontal, vertical and diagonal at \(45^\circ \) line-segments. For such drawings to be readable, special care is needed in order to keep the number of bends small. As the problem of finding planar octilinear drawings of minimum number of bends is NP-hard, in this paper we focus on upper and lower bounds. From a recent result of Keszegh et al. on the slope number of planar graphs, we can derive an upper bound of \(4n-10\) bends for 8-planar graphs with n vertices. We considerably improve this general bound and corresponding previous ones for triconnected 4-, 5- and 6-planar graphs. We also derive non-trivial lower bounds for these three classes of graphs by a technique inspired by the network flow formulation of Tamassia.
This work has been supported by DFG grant Ka812/17-1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note, however, that not all of them can be simultaneously be occupied due to the degree restriction.
- 2.
Except for vertex \(v_1\) of the first partition \(P_0\) of \(\varPi \), which has no outgoing blue edge.
References
Badent, M., Brandes, U., Cornelsen, S.: More canonical ordering. J. Graph Algorithms Appl. 15(1), 97–126 (2011)
Bekos, M.A., Gronemann, M., Kaufmann, M., Krug, R.: Planar octilinear drawings with one bend per edge. J. Graph Algorithms Appl. 19(2), 657–680 (2015)
Bekos, M.A., Kaufmann, M., Krug, R.: On the total number of bends for planar octilinear drawings. Arxiv report arxiv.org/abs/1512.04866 (2014)
Biedl, T.C.: New lower bounds for orthogonal graph drawings. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 28–39. Springer, Heidelberg (1996)
Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998)
Bodlaender, H.L., Tel, G.: A note on rectilinearity and angular resolution. J. Graph Algorithms Appl. 8(1), 89–94 (2004)
De Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)
Di Giacomo, E., Liotta, G., Montecchiani, F.: The Planar Slope Number of Subcubic Graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 132–143. Springer, Heidelberg (2014)
Felsner, S.: Schnyder woods or how to draw a planar graph? In: Geometric Graphs and Arrangements, pp. 17–42. Advanced Lectures in Mathematics, Vieweg/Teubner Verlag (2004)
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)
Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)
Kant, G.: Drawing planar graphs using the lmc-ordering. In: FOCS, pp. 101–110. IEEE (1992)
Kant, G.: Hexagonal grid drawings. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 263–276. Springer, Heidelberg (1993)
Keszegh, B., Pach, J., Pálvölgyi, D.: Drawing planar graphs of bounded degree with few slopes. SIAM J. Discrete Math. 27(2), 1171–1183 (2013)
Liu, Y., Morgana, A., Simeone, B.: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Appl. Math. 81(1–3), 69–91 (1998)
Nöllenburg, M.: Automated drawings of metro maps. Technical Report 2005–25, Fakultät für Informatik, Universität Karlsruhe (2005)
Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)
Tamassia, R., Tollis, I.G., Vitter, J.S.: Lower bounds for planar orthogonal drawings of graphs. Inf. Process. Lett. 39(1), 35–40 (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bekos, M.A., Kaufmann, M., Krug, R. (2016). On the Total Number of Bends for Planar Octilinear Drawings. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-662-49529-2_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49528-5
Online ISBN: 978-3-662-49529-2
eBook Packages: Computer ScienceComputer Science (R0)