Abstract
It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree Δ. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most O(Δ 5). In particular, we answer the question of Dujmović et al. (Comput Geom 38(3):194–212, 2007) whether there is a function f such that plane maximal outerplanar graphs can be drawn using at most f(Δ) slopes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barát J., Matoušek J., Wood D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Combin. 13, R3 (2006)
Dujmović, V., Suderman, M., Wood, D.R.: Really straight graph drawings. In: Graph Drawings 2004. LNCS, vol. 3383, pp. 122–132 (2004)
Dujmović V., Suderman M., Wood D.R.: Graph drawings with few slopes. Comput. Geom. 38, 181–193 (2007)
Dujmović V., Eppstein D., Suderman M., Wood D.R.: Drawings of planar graphs with few slopes and segments. Comput. Geom. 38, 194–212 (2007)
Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B., Tesař, M., Vyskočil, T.: The planar slope number of planar partial 3-trees of bounded degree. In: Graph Drawing 2009. LNCS, vol. 5849, pp. 304–314 (2010)
Fáry I.: On straight-line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229–233 (1948)
Keszegh, B., Pach, J., Pálvölgyi, D., Tóth, G.: Drawing cubic graphs with at most five slopes. In: Graph Drawing 2006. LNCS, vol. 4372, pp. 114–125 (2007)
Keszegh, B., Pach, J., Pálvölgyi, D.: Drawing planar graphs of bounded degree with few slopes. In:~Graph Drawing 2010. LNCS, vol. 6502, pp. 293–304 (2011)
Kratochvíl, J., Vaner, M.: Planar and projective planar embeddings of partial 3-trees (2012, in preparation)
Mukkamala P., Szegedy M.: Geometric representation of cubic graphs with four directions. Comput. Geom. 42, 842–851 (2009)
Mukkamala, P., Pálvölgyi, D.: Drawing cubic graphs with the four basic slopes. In: Graph Drawing 2011. LNCS, vol. 7034, pp. 254–265 (2012)
Pach J., Pálvölgyi D.: Bounded-degree graphs can have arbitrarily large slope numbers. Electr. J. Combin. 13, N1 (2006)
Wade G.A., Chu J.-H.: Drawability of complete graphs using a minimal slope set. Comput. J. 37, 139–142 (1994)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by GraDR EUROGIGA project GIG/11/E023, by project 1M0021620838 of the Czech Ministry of Education, and by Grant 1M0545 of the Czech Ministry of Education.
Rights and permissions
About this article
Cite this article
Jelínek, V., Jelínková, E., Kratochvíl, J. et al. The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree. Graphs and Combinatorics 29, 981–1005 (2013). https://doi.org/10.1007/s00373-012-1157-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-012-1157-z