mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

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

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

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 line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...

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 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. intersect1.png, Figure 1 intersect2.png, Figure 2 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 shar ...

follows. proved that some planar graphs cannot be represented in that way. 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 mathematics, mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle graph, triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique (graph t ...

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

Grötzsch's theorem In the mathematics, mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free graph, triangle-free planar graph can be graph coloring, colored with only three colors. According to the four-color theorem, eve ...

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 g ...

, 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 , last1=Gonçalves , first1=Daniel , title=Not all planar graphs are in PURE-4-DIR , journal=Journal of Graph Algorithms and Applications , date=2020 , volume=24 , issue=3 , pages=293–301 , doi=10.7155/jgaa.00533, doi-access=free . Statements about planar graphs Conjectures that have been proved