points. When is not prime, one can perform this construction for a grid contained in the grid, where is the largest prime that is at Because the gap between consecutive primes is much smaller than the primes themselves, will always be close so this method can be used to place points in the grid with no three points collinear. Erdős' bound has been improved subsequently: show that, when is prime, one can obtain a solution with points, by placing points in multiple copies of the hyperbola where may be chosen arbitrarily as long as it is nonzero Again, for arbitrary one can perform this construction for a prime near to obtain a solution with Upper bound At most points may be placed in a grid of any For, if more points are placed, then by the pigeonhole principle some three of them would all lie on the same horizontal line of the grid. For , this trivial bound is known to be tight. Conjectured bounds Although exactly points can be placed on small grids, conjectured that for large grids, there is a significantly smaller upper bound on the number of points that can be placed. More precisely, they conjectured that the number of points that can be placed is at most a sublinear amount larger with After an error in the heuristic reasoning leading to this conjecture was uncovered, Guy corrected the error and made the stronger conjecture that one cannot do more than sublinearly better than with Applications Solutions to the no-three-in-line problem can be used to avoid certain kinds of degeneracies in graph drawing. The problem they apply to involves placing the vertices of a given graph at integer coordinates in the plane, and drawing the edges of the graph as straight line segments. For certain graphs, such as the utility graph, crossings between pairs of edges are unavoidable, but one should still avoid placements that cause a vertex to lie on an edge through two other vertices. When the vertices are placed with no three in line, this kind of problematic placement cannot occur, because the entire line through any two vertices, and not just the line segment, is free of other vertices. The fact that the no-three-in-line problem has a solution with linearly many points can be translated into graph drawing terms as meaning that every graph, even a complete graph, can be drawn without unwanted