Гипотеза Шейнермана

Гипотеза Шейнермана, теперь доказанная теорема, утверждает, что любой планарный граф является графом пересечений набора отрезков на плоскости. Эту гипотезу сформулировал Эдвард Шейнерман в своей кандидатской диссертации, следуя более раннему результату, что любой планарный граф можно представить как граф пересечений простых кривых на плоскости. Теорему доказали Чалопин и Гонсалвис.

Пример

Например, граф G, показанный ниже слева может быть представлен как граф пересечений набора отрезков, показанных справа. Здесь вершины графа G представлены отрезками, а рёбра графа G представлены точками пересечений этих отрезков.

Развитие

Шейнерман также высказал гипотезу, что достаточно иметь отрезки трёх направлений для представления раскрашиваемых в 3 цвета графов, а Вест высказал гипотезу, что, аналогично, любой планарный граф может быть представлен с помощью отрезков четырёх направлений. Если граф представим отрезками, имеющими только k направления, и никакие два отрезка не лежат на одной прямой, граф можно выкрасить с помощью k цветов, по одному цвету на каждое направление. Поэтому, если любой планарный граф может быть представлен таким способом только с четырьмя направлениями отрезков, отсюда будет следовать теорема о четырёх красках.

Хартман, Ньюман и Зив, а также Де Фрейсикс, Оссона де Мендез и Пах, доказали, что любой двудольный планарный граф может быть представлен как граф пресечений горизонтальных и вертикальных отрезков. См. об этом статью Чижовича, Кранакиса и Уррутия. Де Кастро, Кобос, Дана и Маркес доказали, что любой свободный от треугольников планарный граф может быть представлен как граф пересечений отрезков, имеющих всего три направления. Из их результата вытекает теорема Грёча, что свободные от треугольников планарные графы могут быть раскрашены в три цвета. Де Фрейсикс и Оссона де Мендез доказали, что если планарный граф G может быть раскрашен в 4 цвета так, что никакой разделяющий цикл не использует все четыре цвета, то граф G имеет представление как граф пересечений отрезков.

Струнные графы

Чалопин, Гонсалвис и Очем доказали, что планарные графы находятся в классе 1-СТРУН, классе графов пересечений простых кривых на плоскости, которые пересекают друг друга максимум один раз на пару кривых. Этот класс является средним между графами пересечений отрезков, появляющихся в гипотезе Шейнерман, и графами пересечений простых кривых без ограничений из результатов Эрлиха (и его соавторов). Гипотезу можно рассматривать как обобщение теоремы об упаковке кругов, которая даёт тот же результат, когда кривые могут только касаться друг друга. Доказательство гипотезы, которое дали Чалопин и Гонсалвис базировалось на улучшении этого результата.