Drawing Planar Graphs of Bounded Degree with Few Slopes

Keszegh, Balázs and Pach, János and Palvölgyi, Dömötör (2011) Drawing Planar Graphs of Bounded Degree with Few Slopes. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 293-304 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_27).

Full text not available from this repository.

Abstract

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different slopes. If we allow the edges to be represented by polygonal paths with one bend, then 2d slopes suffice. Allowing two bends per edge, every planar graph with maximum degree d_> 3 can be drawn using segments of at most [d/2] different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. These bounds cannot be improved.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_27
Classifications:P Styles > P.999 Others
ID Code:1215

Repository Staff Only: item control page

References

Barát, J., Matoušek, J., Wood, D.: Bounded-degree graphs have arbitrarily large geometric thickness. Electronic J. Combinatorics 13(1) (2006) R3

Biedl, T., Kant, G.: A better heuristic for onthogonal graph drawings, Comput. Comput. Geom. 9, 159–180 (1998)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)

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, 181–193 (2007)

Duncan, C.A., Eppstein, D., Kobourov, S.G.: The geometric thickness of low degree graphs. In: Proc. 20th ACM Symp. on Computational Geometry (SoCG 2004), pp. 340–346. ACM Press, New York (2004)

Engelstein, M.: Drawing graphs with few slopes, Research paper submitted to the Intel Competition for high school students, New York (October 2005)

Eppstein, D.: Separating thickness from geometric thickness. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs, Contemporary Mathematics, Amer. Math. Soc., Providence, pp. 75–86 (2004)

Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229–233 (1948)

de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Combinatorics, Probability and Computing 3, 233–246 (1994)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Garg, A., Tamassia, R.: Planar drawings and angular resolution: Algorithms and bounds. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 12–23. Springer, Heidelberg (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. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 304–315. Springer, Heidelberg (2010)

Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte Verhand. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Klasse 88, 141–164 (1936)

Keszegh, B., Pach, J., Plvlgyi, D., Tth, G.: Drawing cubic graphs with at most five slopes, Drawing cubic graphs with at most five slopes. Comput. Geom. 40(2), 138–147 (2008)

Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Rosenstiehl, P. (ed.) Theory of Graphs, pp. 215–232. Gordon and Breach, New York (1967)

Liu, Y., Morgana, A., Simeone, B.: General theoretical results on rectilinear embeddability of graphs. Acta Math. Appl. Sinica 7, 187–192 (1991)

Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. SIAM J. Discrete Math. 7, 172–183 (1994)

Mukkamala, P., Szegedy, M.: Geometric representation of cubic graphs with four directions. Comput. Geom. 42, 842–851 (2009)

Pach, J., Pálvölgyi, D.: Bounded-degree graphs can have arbitrarily large slope numbers. Electronic J. Combinatorics 13(1) (2006) N1

Pach, J., Tóth, G.: Crossing number of toroidal graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 334–342. Springer, Heidelberg (2006)

Ungar, P.: On diagrams representing maps. J. London Math. Soc. 28, 336–342 (1953)

Wade, G.A., Chu, J.H.: Drawability of complete graphs using a minimal slope set. The Computer J. 37, 139–142 (1994)