Representing Graphs by Intersecting Line Segments
Let L be a collection of line segments in the plane. Form a graph G = G(L) whose vertices are the segments in L and whose edges join those line segments which cross each other.
Problem: Is every planar graph G representable by intersecting line segments?
The problem was introduced by Scheinerman [S] who proved that every outerplanar graph was so representable. Hartman, Newman, and Ziv [HNZ] proved that every bipartite planar graph is so representable using segments of only two slopes.
A stronger conjecture is due to Doug West [W]:
Problem: Is every planar graph representable by intersecting line segments of four different slopes?
As this implies the Four Color Theorem, the proof is expected to be difficult. Scheinerman also asks about representating three-colorable graphs:
Problem: Is every 3-colorable planar graph representable by intersecting line segments of three different slopes?
When this problem was originally proposed, it was unknown if every 3-colorable planar graph was representable by intersecting line segments, even without the restriction to only 3 slopes. However, I recently heard from Patrice Ossona de Mendez and Hubert de Fraysseix that they have shown [dMdF] that any 4-colored planar graph without an induced cycle of length 4 using all four colors is representable by intersecting line segments. This class includes 3-colorable planar graphs.
[dMdF] P. O. de Mendez and H. de Fraysseix, Contact and interval representations, to appear Algorithmica
[HNZ] I.B.A. Hartman, I. Newman, and R. Ziv, On grid intersection graphs, Discrete Math. 87 (1991) 42-52.
[S] E.R. Scheinerman, Intersection classes and
multiple intersection parameters of graphs, Ph.D. Thesis,
[W] D. West, Open problems,
Submitted by: Dan Archdeacon, Department of Mathematics
Send comments to email@example.com
August 1995, slightly modified December 2003 and November 2004