Теорема Фари говорит, что простой планарный граф можно нарисовать без пересечений, так что каждое ребро является отрезком прямой.
Мой вопрос заключается в том, существует ли аналогичная теорема для графов ограниченного числа пересечений . В частности, можем ли мы сказать, что простой график с числом пересечений k можно нарисовать так, чтобы на чертеже было k пересечений и чтобы каждое ребро представляло собой кривую степени не более f (k) для некоторой функции f?
РЕДАКТИРОВАТЬ: Как отмечает Дэвид Эппштейн, легко видеть, что теорема Фари подразумевает рисование графа с числом пересечения k, так что каждое ребро является многоугольной цепью с не более чем k изгибов. Мне все еще интересно, можно ли нарисовать каждое ребро с помощью кривых с ограниченным градусом. Сянь-Чи Чанг указывает, что f (k) = 1, если k равно 0, 1, 2, 3, и f (k)> 1 в противном случае.
Это известно как прямолинейное число пересеченияcr¯¯¯¯(G) , что является минимальным количеством пересечений среди всех возможных прямолинейных рисунков графика G , Сравните с нормальным числом пересеченияcr(G) можно увидеть, что cr¯¯¯¯(G)≥cr(G) , И ваш вопрос по сути такой же, как вопросcr¯¯¯¯(G)=cr(G) если cr(G)≤k для некоторой константы k ,
В статье « Границы прямолинейных чисел пересечения» Бинсток и Дин доказали, что
См . Опрос о пересечении чисел Рихтера и Салазара для справки. Таким образом, если существует вариант теоремы Фари о графах с ограниченными числами пересечения, он должен быть ограниченcr(G)≤3 ,
Для небольшого примера сcr¯¯¯¯(G)≠cr(G) рассмотрим полный граф на 8 вершинах. В нем естьcr(K8)=18 а также cr¯¯¯¯(K8)=19 ,
источник