Abstract
We consider drawings of graphs in the plane in which edges are represented by polygonal paths with at most one bend and the number of different slopes used by all segments of these paths is small. We prove that \(\lceil \frac{\varDelta }{2}\rceil \) edge slopes suffice for outerplanar drawings of outerplanar graphs with maximum degree \(\varDelta \geqslant 3\). This matches the obvious lower bound. We also show that \(\lceil \frac{\varDelta }{2}\rceil +1\) edge slopes suffice for drawings of general graphs, improving on the previous bound of \(\varDelta +1\). Furthermore, we improve previous upper bounds on the number of slopes needed for planar drawings of planar and bipartite planar graphs.
K. Knauer—Supported by ANR EGOS grant ANR-12-JS02-002-01 and PEPS grant EROS.
B. Walczak—Supported by MNiSW grant 911/MOB/2012/0.
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
References
Barát, J., Matoušek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Combin. 13(1), #R3, 14 pp. (2006)
Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1994)
Czyzowicz, J.: Lattice diagrams with few slopes. J. Combin. Theory, Ser. A 56(1), 96–108 (1991)
Czyzowicz, J., Pelc, A., Rival, I., Urrutia, J.: Crooked diagrams with few slopes. Order 7(2), 133–143 (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)
Dujmović, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs with few slopes and segments. Comput. Geom. 38(3), 194–212 (2007)
Dujmović, V., Suderman, M., Wood, D.R.: Graph drawings with few slopes. Comput. Geom. 38(3), 181–193 (2007)
Dujmović, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 339–358 (2004)
Felsner, S., Kaufmann, M., Valtr, P.: Bend-optimal orthogonal graph drawing in the general position model. Comput. Geom. 47(3), 460–468 (2014)
de Fraysseix, H., de Mendez, P.O., Pach, J.: A left-first search algorithm for planar graphs. Discrete Comput. Geom. 13(3–4), 459–468 (1995)
de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Combin. Prob. Comput. 3(2), 233–246 (1994)
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. Graphs Combin. 29(4), 981–1005 (2013)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)
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)
Keszegh, B., Pach, J., Pálvölgyi, D., Tóth, G.: Drawing cubic graphs with at most five slopes. Comput. Geom. 40(2), 138–147 (2008)
Knauer, K., Micek, P., Walczak, B.: Outerplanar graph drawings with few slopes. Comput. Geom. 47(5), 614–624 (2014)
Lenhart, W., Liotta, G., Mondal, D., Nishat, R.I.: Planar and plane slope number of partial 2-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 412–423. Springer, Heidelberg (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)
Misra, J., Gries, D.: A constructive proof of Vizing’s theorem. Inform. Process. Lett. 41(3), 131–133 (1992)
Mukkamala, P., Pálvölgyi, D.: Drawing cubic graphs with the four basic slopes. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 254–265. Springer, Heidelberg (2012)
Mukkamala, P., Szegedy, M.: Geometric representation of cubic graphs with four directions. Comput. Geom. 42(9), 842–851 (2009)
Nomura, K., Tayu, S., Ueno, S.: On the orthogonal drawing of outerplanar graphs. In: Chwa, K.-Y., Munro, J.I. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 300–308. Springer, Heidelberg (2004)
Pach, J., Pálvölgyi, D.: Bounded-degree graphs can have arbitrarily large slope numbers. Electron. J. Combin. 13(1), #N1, 4 pp. (2006)
Vizing, V.G.: Ob otsenke khromaticheskogo klassa \(p\)-grafa (On an estimate of the chromatic class of a \(p\)-graph). Diskret. Analiz 3, 25–30 (1964)
Wade, G.A., Chu, J.H.: Drawability of complete graphs using a minimal slope set. Comput. J. 37(2), 139–142 (1994)
Acknowledgment
We are grateful to Piotr Micek for fruitful discussions.
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
Knauer, K., Walczak, B. (2016). Graph Drawings with One Bend and Few Slopes. 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_41
Download citation
DOI: https://doi.org/10.1007/978-3-662-49529-2_41
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)