# Slope number

A drawing of the Petersen graph with slope number 3

In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.

## Complete graphs

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.

## Relation to degree

The slope number of a graph of maximum degree d is clearly at least $\lceil d/2\rceil$, because at most two of the incident edges at a degree-d vertex can share a slope. More precisely, the slope number is at least equal to the linear arboricity of the graph, since the edges of a single slope must form a linear forest, and the linear arboricity in turn is at least $\lceil d/2\rceil$.

There exist graphs with maximum degree five that have arbitrarily large slope number.[1] However, every graph of maximum degree three has slope number at most four;[2] the result of Wade & Chu (1994) for the complete graph K4 shows that this is tight. Not every set of four slopes is suitable for drawing all degree-3 graphs: a set of slopes is suitable for this purpose if and only it forms the slopes of the sides and diagonals of a parallelogram. 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.[3] It is not known whether graphs of maximum degree four have bounded or unbounded slope number.[4]

The method of Keszegh, Pach & Pálvölgyi (2011) for combining circle packings and quadtrees to achieve bounded slope number for planar graphs with bounded degree

## Planar graphs

As Keszegh, Pach & Pálvölgyi (2011) showed, every planar graph has a planar straight-line drawing in which the number of distinct slopes is a function of the degree of the graph. Their proof follows a construction of Malitz & Papakostas (1994) for bounding the angular resolution of planar graphs as a function of degree, by completing the graph to a maximal planar graph without increasing its degree by more than a constant factor, and applying the circle packing theorem to represent this augmented graph as a collection of tangent circles. If the degree of the initial graph is bounded, the ratio between the radii of adjacent circles in the packing will also be bounded,[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.

## Complexity

It is NP-complete to determine whether a graph has slope number two.[6] From this, it follows that it is NP-hard to determine the slope number of an arbitrary graph, or to approximate it with an approximation ratio better than 3/2.

It is also NP-complete to determine whether a planar graph has a planar drawing with slope number two.[7]

## Notes

1. ^ Proved independently by Barát, Matoušek & Wood (2006) and Pach & Pálvölgyi (2006), solving a problem posed by Dujmović, Suderman & Wood (2005). See theorems 5.1 and 5.2 of Pach & Sharir (2009).
2. ^ Mukkamala & Szegedy (2009), improving an earlier result of Keszegh et al. (2008); theorem 5.3 of Pach & Sharir (2009).
3. ^
4. ^
5. ^
6. ^
7. ^