В математике гипотеза Шайнермана , ставшая теперь теоремой, утверждает, что каждый плоский граф является графом пересечения набора отрезков прямой на плоскости. Эту гипотезу сформулировал Э.Р. Шейнерман в своей докторской диссертации. диссертация (1984), следуя более ранним результатам о том, что каждый плоский граф может быть представлен как граф пересечений набора простых кривых на плоскости (Эрлих, Эвен и Тарьян, 1976). Это доказали Жереми Чалопен и Даниэль Гонсалвес (2009).
Например, граф G , показанный ниже слева, может быть представлен как граф пересечений набора сегментов, показанных ниже справа. Здесь вершины G представлены отрезками прямых, а ребра G представлены точками пересечения.
Шайнерман также предположил, что сегментов только с тремя направлениями будет достаточно для представления графов, раскрашиваемых в 3 цвета , а Уэст (1991) предположил, что аналогичным образом каждый планарный граф можно представить с использованием четырех направлений. Если граф представлен сегментами, имеющими только k направлений и никакие два сегмента не принадлежат одной прямой, то граф можно раскрасить k цветов, по одному цвету для каждого направления. Следовательно, если каждый плоский граф можно представить таким образом только с четырьмя направлениями, то отсюда следует теорема о четырех цветах .
Хартман, Ньюман и Зив (1991) и де Фрессейкс, Оссона де Мендес и Пах (1991) доказали, что каждый двудольный плоский граф может быть представлен как граф пересечения горизонтальных и вертикальных отрезков; об этом результате см. также Czyzowicz, Kranakis & Urrutia (1998). Де Кастро и др. (2002) доказали, что каждый планарный граф без треугольников можно представить как граф пересечений отрезков прямой, имеющих только три направления; из этого результата следует теорема Греча (Grötzsch 1959) о том, что плоские графы без треугольников можно раскрасить в три цвета. де Фрайссейкс и Оссона де Мендес (2005) доказали, что если планарный граф G может быть 4-цветным таким образом, что ни один разделяющий цикл не использует все четыре цвета, то G имеет представление в виде графа пересечений сегментов.
Chalopin, Gonçalves & Ochem (2007) доказали, что плоские графы относятся к 1-STRING, классу графов пересечений простых кривых на плоскости, которые пересекаются друг с другом не более чем в одной точке пересечения на пару. Этот класс занимает промежуточное положение между графами пересечений отрезков, возникающими в гипотезе Шейнермана, и графами пересечений неограниченных простых кривых из результата Эрлиха и др. Ее также можно рассматривать как обобщение теоремы об упаковке кругов , которая показывает тот же результат, когда кривым разрешено пересекаться по касательной. Доказательство гипотезы Чалопина и Гонсалвеса (2009) было основано на улучшении этого результата.