Cubic Graphs Have Bounded Slope Parameter

Keszegh, Balázs and Pach, János and Pálvölgyi, Dömötör and Tóth, Géza (2009) Cubic Graphs Have Bounded Slope Parameter. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 50-60 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_6).

Full text not available from this repository.

Abstract

We show that every finite connected graph G with maximum degree three and with at least one vertex of degree smaller than three has a straight-line drawing in the plane satisfying the following conditions. No three vertices are collinear, and a pair of vertices form an edge in G if and only if the segment connecting them is parallel to one of the sides of a previously fixed regular pentagon. It is also proved that every finite graph with maximum degree three permits a straight-line drawing with the above properties using only at most seven different edge slopes.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_6
Classifications:P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
ID Code:894

Repository Staff Only: item control page

References

Ambrus, G., Bárat, J., Hajnal, P.: The slope parameter of graphs. Acta Sci. Math. (Szeged) 72, no. 3–4, 875–889 (2006)

Bárat, J., Matousek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electr. J. Combin. 13, no. 1, R3, 14 pp. (2006)

Dillencourt, M.B., Eppstein,D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms Appl. 4(3), 5-17 (2000)

Dujmovic, V., Suderman, M., Wood, D.R.: Graph drawings with few slopes. Comput. Geom. 38, 181-193 (2007)

Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thickness parameters. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 129-140. Springer, Berlin (2006)

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

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

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

Hutchinson, J.P., Shermer, T.C., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. 13, 161-171 (1999)

Jamison, R.E.: Few slopes without collinearity. Discrete Math. 60, 199-206 (1986) 11. Kainen, P.C.: Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg 39, 88– 95 (1973)

Keszegh, B., Pach, J., Palvolgyi, D., Toth, G.: Drawing cubic graphs with at most five slopes. In: Graph Drawing 2006. LNCS vol. 4372, 114–125. Springer-Verlag, (2007)

Mukkamala, P., Szegedy, M.: Geometric representation of cubic graphs with four directions. Manuscript, (2007)

Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: a survey. Graphs Combin. 14, 59–73 (1998)

Pach, J., Palvolgyi, D.: Bounded-degree graphs can have arbitrarily large slope numbers. Electr. J. Combin. 13, no. 1, Note 1, 4 pp. (2006)

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