mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, Scheinerman's conjecture, now a theorem, states that every

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

is the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

of a set of

line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...

s 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 . It was proven by . For instance, the graph ''G'' shown below to the left may be represented as the intersection graph of the set of segments shown below to the right. 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 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. Therefore, if every planar graph can be represented in this way with only four directions, then the

four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...

follows. and proved that every bipartite planar graph can be represented as an intersection graph of horizontal and vertical line segments; for this result see also . proved that every

triangle-free In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...

planar graph can be represented as an intersection graph of line segments having only three directions; this result implies

Grötzsch's theorem GR may refer to: Arts, entertainment, and media Film and television * ''Golmaal Returns'', a 2008 Bollywood film * ''Generator Rex'', an animated TV series * Guilty Remnant, a cult-like organization portrayed in '' The Leftovers'', an HBO televis ...

that triangle-free planar graphs can be colored with three colors. proved that if a planar graph ''G'' can be 4-colored in such a way that no separating cycle uses all four colors, then ''G'' has a representation as an intersection graph of segments. proved that planar graphs are in 1-STRING, the class of intersection graphs of simple curves in the plane that intersect each other in at most one crossing point per pair. This class is intermediate between the intersection graphs of segments appearing in Scheinerman's conjecture and the intersection graphs of unrestricted simple curves from the result of Ehrlich et al. It can also be viewed as a generalization of the

circle packing theorem The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...

, which shows the same result when curves are allowed to intersect in a tangent. The proof of the conjecture by was based on an improvement of this result.

References

*. *. *. *. *. *. *. *. *. *. *{{citation , last = West , first = D. , authorlink = Douglas West (mathematician) , issue = 1 , journal = SIAM Activity Group Newsletter in Discrete Mathematics , pages = 10–12 , title = Open problems #2 , volume = 2 , year = 1991. Planar graphs Conjectures that have been proved