Slope number

Although closely related problems in discrete geometry had been studied earlier, e.g. by Scott (1970) and Jamison (1984), the problem of determining the slope number of a graph was introduced by Wade & Chu (1994), who showed that the slope number of an n-vertex complete graph Kn is exactly n. A drawing with this slope number may be formed by placing the vertices of the graph on a regular polygon.

There exist graphs with maximum degree five that have arbitrarily large slope number.

In particular, any degree 3 graph can be drawn so that its edges are either axis-parallel or parallel to the main diagonals of the integer lattice.

If the degree of the initial graph is bounded, the ratio between the radii of adjacent circles in the packing will also be bounded by the ring lemma,[5] which in turn implies that using a quadtree to place each graph vertex on a point within its circle will produce slopes that are ratios of small integers.

The number of distinct slopes produced by this construction is exponential in the degree of the graph.