Построение графиков ограниченного пересечения числа

9

Теорема Фари говорит, что простой планарный граф можно нарисовать без пересечений, так что каждое ребро является отрезком прямой.

Мой вопрос заключается в том, существует ли аналогичная теорема для графов ограниченного числа пересечений . В частности, можем ли мы сказать, что простой график с числом пересечений k можно нарисовать так, чтобы на чертеже было k пересечений и чтобы каждое ребро представляло собой кривую степени не более f (k) для некоторой функции f?

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

Арнаб
источник

Ответы:

12

Если граф имеет ограниченное число пересечений, его можно нарисовать с таким количеством пересечений в модели ломаной линии (т. Е. Каждое ребро является многоугольной цепью, гораздо более распространенной в литературе по рисованию графа, чем алгебраические кривые ограниченной степени) с ограниченным числом изгибов. по краю Это также справедливо в более общем смысле, если число ребер ограничено. Чтобы увидеть это, просто выровняйте график (замените каждое пересечение вершиной), а затем примените Фари.

Теперь, чтобы использовать это, чтобы ответить на ваш реальный вопрос, вам нужно найти алгебраическую кривую, произвольно близкую к заданной полилинии, со степенью, ограниченной функцией числа изгибов полилинии. Это также можно сделать довольно легко. Например: для каждого сегментаsi полилинии, пусть ei быть эллипсом с высоким эксцентриситетом, который очень близок к si, и разреши pi быть квадратичным полиномом, который положителен снаружи ei и отрицательный внутри ei, Пусть ваш общий полином принимает формуp=ϵipi где ϵэто небольшое положительное вещественное число. Тогда один компонент кривойp=0будет немного лежать вне объединения эллипсов и может использоваться для замены ломаной линии; его степень будет в два раза больше числа эллипсов, которое является линейным по количеству пересечений на ребро.

Дэвид Эппштейн
источник
2
Спасибо. Есть ли пример, который показывает, что вообще нельзя рисовать с минимальным количеством пересечений, используя края отрезка прямой линии?
Арнаб
@arnab: см. ответ Сянь-Цзи.
Дэвид Эппштейн
12

Это известно как прямолинейное число пересечения cr¯(G), что является минимальным количеством пересечений среди всех возможных прямолинейных рисунков графика G, Сравните с нормальным числом пересеченияcr(G)можно увидеть, что cr¯(G)cr(G), И ваш вопрос по сути такой же, как вопросcr¯(G)=cr(G) если cr(G)k для некоторой константы k,

В статье « Границы прямолинейных чисел пересечения» Бинсток и Дин доказали, что

Теорема. Еслиk3, у нас есть cr¯(G)=cr(G), И дляk4есть графики Gn с cr(G)=4 а также cr¯(G)n,

См . Опрос о пересечении чисел Рихтера и Салазара для справки. Таким образом, если существует вариант теоремы Фари о графах с ограниченными числами пересечения, он должен быть ограниченcr(G)3,

Для небольшого примера с cr¯(G)cr(G)рассмотрим полный граф на 8 вершинах. В нем естьcr(K8)=18 а также cr¯(K8)=19,

Сянь-Чжи Чан 張顯 之
источник
Спасибо! Это тогда отвечает на вопрос в моем комментарии к ответу Дэвида. Мне все еще интересно узнать, был ли изучен мой оригинальный вопрос.
Арнаб