Scheinerman's conjecture
Encyclopedia
In mathematics
, Scheinerman's conjecture, now a theorem, states that every planar graph
is the intersection graph
of a set of line segment
s in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis Scheinerman, 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
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
planar graph can be represented as an intersection graph of line segments having only three directions; this result implies Grötzsch's theorem
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
, 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Scheinerman's conjecture, now a theorem, states that every planar graph
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...
is the intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of a set of line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis Scheinerman, 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
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
of G are represented by straight line segments and edges
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
of G are represented by intersection points.
Scheinerman also conjectured that segments with only three directions would be sufficient to represent 3-colorable
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
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
Four color theorem
In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...
follows.
and proved that every bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
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
Triangle-free graph
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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
planar graph can be represented as an intersection graph of line segments having only three directions; this result implies Grötzsch's theorem
Grötzsch's theorem
In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors...
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
String graph
In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the...
from the result of Ehrlich et al. It can also be viewed as a generalization of the circle packing theorem
Circle packing theorem
The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint...
, 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.