Scheinerman's conjecture

In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis (1984), following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane (Sinden 1966) (Ehrlich, Even & Tarjan 1976). It was proven by Jeremie Chalopin and Daniel Gonçalves (2009). For instance, the graph G shown in figure 1 may be represented as the intersection graph of the set of segments shown in figure 2. Here, vertices of G are represented by straight line segments and edges of G are represented by intersection points. Scheinerman also conjectured that segments with only three directions would be sufficient to represent 3-colorable graphs, and West (1991) conjectured that analogously every planar graph could be represented using four directions. If a graph is represented with segments having only k directions and no two segments belong to the same line, then the graph can be colored using k colors, one color for each direction.