Drawing cubic graphs with at most five slopes

Keszegh, Balázs and Pach, János and Pálvölgyi, Dömötör and Tóth, Géza (2007) Drawing cubic graphs with at most five slopes. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 114-125 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_13).

Full text not available from this repository.

Abstract

We show that every graph G with maximum degree three has a straight-line drawing in the plane using edges of at most five different slopes. Moreover, if G is connected and has at least one vertex of degree less than three, then four directions suffice.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_13
Classifications:P Styles > P.720 Straight-line
ID Code:767

Repository Staff Only: item control page

References

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

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

V. Dujmovic, M. Suderman, and D.R. Wood: Really straight graph drawings, in: Graph Drawing (GD'04), J. Pach, ed., Lecture Notes in Computer Science 3383, Springer-Verlag, Berlin, 2005, 122-132.

C. A. Duncan, D. Eppstein, and S.G. Kobourov: The geometric thickness of low degree graphs, in: Proc. 20th ACM Symp. on Computational Geometry (SoCG'04), ACM Press, 2004, 340-346.

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

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

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

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

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