vertex-edge incidences using a grid whose area is quadratic in the number of vertices, and that for complete graphs no such drawing with less than quadratic area is possible. The complete graphs also require a linear number of colors in any graph coloring, but other graphs that can be colored with fewer colors can also be drawn on smaller grids: if a graph has vertices and a graph coloring with colors, it can be drawn in a grid with area proportional The no-three-in-line drawing of a complete graph is a special case of this result The no-three-in-line problem also has applications to another problem in discrete geometry, the Heilbronn triangle problem. In this problem, one must place points, anywhere in a unit square, not restricted to a grid. The goal of the placement is to avoid small-area triangles, and more specifically to maximize the area of the smallest triangle formed by three of the points. For instance, a placement with three points in line would be very bad by this criterion, because these three points would form a degenerate triangle with area zero. On the other hand, if the points can be placed on a grid of side length within the unit square, with no three in a line, then by Pick's theorem every triangle would have area at half of a grid square. Therefore, solving an instance of the no-three-in-line problem and then scaling down the integer grid to fit within a unit square produces solutions to the Heilbronn triangle problem where the smallest triangle has area This application was the motivation for Paul Erdős to find his solution for the no-three-in-line problem. It remained the best area lower bound known for the Heilbronn triangle problem from 1951 until 1982, when it was improved by a logarithmic factor using a construction that was not based on the no-three-in-line problem. Generalizations and variations General-position subsets In computational geometry, finite sets of points with no three in line are said to be in general position. In this terminology, the no-three-in-line problem seeks the largest subset of a grid that is in general position, but researchers have also considered the problem of finding the largest general position subset of other non-grid sets of points. It is NP-hard to find this subset, for certain input sets, and hard to approximate its size to within a constant factor; this hardness of approximation result is