В математике гипотеза Шейнермана, ставшая теперь теоремой, утверждает, что каждый планарный граф является графом пересечения набора отрезков на плоскости. Эта гипотеза была сформулирована Э. Р. Шейнерманом в его докторской диссертации. диссертацию (1984) , следуя более ранним результатам о том, что каждый планарный граф может быть представлен как граф пересечения набора простых кривых на плоскости ( Ehrlich, Even & Tarjan 1976 ). Это доказали Жереми Шалопен и Даниэль Гонсалвес ( 2009 ).
Например, граф G , показанный ниже слева, может быть представлен как граф пересечения множества сегментов, показанных ниже справа. Здесь вершины G представлены отрезками прямых, а ребра G представлены точками пересечения.
Шайнерман также предположил, что сегментов только с тремя направлениями будет достаточно для представления 3 - раскрашиваемых графов, а Уэст (1991) предположил, что аналогичным образом каждый планарный граф может быть представлен с использованием четырех направлений. Если граф представлен отрезками, имеющими только k направлений, и никакие два отрезка не принадлежат одной и той же прямой, то граф можно раскрасить k цветами, по одному цвету для каждого направления. Следовательно, если каждый планарный граф может быть представлен таким образом только с четырьмя направлениями, то следует теорема о четырех красках .
Hartman, Newman & Ziv (1991) и de Fraysseix, Ossona de Mendez & Pach (1991) доказали, что каждый двудольный планарный граф может быть представлен как граф пересечения горизонтальных и вертикальных отрезков; об этом результате см. также Czyzowicz, Kranakis & Urrutia (1998) . Де Кастро и др. (2002) доказали, что любой плоский граф без треугольников может быть представлен как граф пересечений отрезков, имеющих только три направления; этот результат вытекает из теоремы Грёча ( Grötzsch 1959 ) о том, что плоские графы без треугольников можно раскрасить тремя цветами. de Fraysseix & Ossona de Mendez (2005) доказали, что если планарный графG можно раскрасить в 4 цвета таким образом, что ни один разделяющий цикл не использует все четыре цвета, тогда G имеет представление в виде графа пересечений отрезков.
Chalopin, Goncalves & Ochem (2007) доказали, что плоские графы относятся к 1-STRING, классу графов пересечений простых кривых на плоскости, которые пересекаются друг с другом не более чем в одной точке пересечения на пару. Этот класс является промежуточным между графами пересечений отрезков, появляющимися в гипотезе Шайнермана, и графами пересечений неограниченных простых кривых из результата Эрлиха и др. Его также можно рассматривать как обобщение теоремы об упаковке кругов , которая показывает тот же результат, когда кривым разрешено пересекаться по касательной. Доказательство гипотезы Chalopin & Goncalves (2009) было основано на улучшении этого результата.