Logo

Login

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. [Conference Paper]

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
Classifications:P Styles > P.720 Straight-line
ID Code:767
Deposited By:GDEA, Administration
Deposited On:04 May 2007
Last Modified:11 Dec 2009 11:55
Alternative Locations:http://www.springer.com/dal/home/computer/lncs?SGWID=1-164-22-173721109-0

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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.