Условия того, что двудольный граф должен быть плоским без ребер, проходящих вокруг вершин

Двудольный граф плоский, если в нем нет или миноров. К $K_{3, 3}$$K_5$

Я ищу необходимые или / и достаточные условия, чтобы плоские чертежи без ребер "обходили" наборы вершин. Это рисунки, удовлетворяющие:

1. Все вершины одной части нарисованы на одной вертикальной линии. Вершины другой части нарисованы на параллельной линии вертикали.
2. Края не пересекаются, кроме как в вершинах.
3. Все края находятся в бесконечной полосе между двумя вертикальными линиями в точке 1.

Например, все рисунки здесь, кроме нижнего правого, не являются примерами. Нижний левый график можно перерисовать в соответствии с условиями, поменяв местами Q и R. Вершины двух графиков не могут быть перерисованы для соответствия условиям.

Два верхних графика - единственные препятствия, которые я смог найти. Мои вопросы:

1. У этой проблемы есть имя?
2. Любые другие препятствия, которые я пропустил?
3. Любые намеки на то, как я могу доказать, что эти два препятствия (наряду со всем, что я пропустил), как несовершеннолетние, конечно, необходимы и достаточны.

Обратите внимание, что это не то же самое, что быть внешнепланарным, является внешнепланарным (можно нарисовать в виде квадрата), но его нельзя нарисовать, чтобы удовлетворить условиям, которые я упоминал выше.$K_{2, 2}$

Ваши графики - это в точности графики ширины пути  или, что эквивалентно, леса, каждый из компонентов которых является гусеницей . Гусеницы имеют две соответствующие характеристики:$1$

• это деревья, в которых есть единственный путь, содержащий каждую вершину степени больше  ;$1$

• это деревья, в которых каждая вершина имеет не более двух соседних листьев.

Лемма 1. Каждая гусеница в вашем классе.

Доказательство. Пусть - гусеница, и пусть - самый длинный путь, содержащий каждую вершину степени  или более. Обратите внимание, что по максимальному значению . Мы можем создать рисунок  , сначала нарисовав  как зигзаг, а затем добавив вершины степени смежные с  между и  . P = x 1 … x ℓ 2 d ( x 1 ) = d ( x ℓ ) = 1 G P 1 x i x i - 1 x i + 1$G$$P=x_1\dots x_\ell$$2$$d(x_1)=d(x_\ell)=1$$G$$P$$1$$x_i$$x_{i-1}$$x_{i+1}$$\Box$

Лемма 2. Каждый граф в вашем классе ацикличен.$G$

Доказательство. Предположим, что содержит цикл и предположим, что он имеет чертеж требуемой формы. Wlog,  выше  . Но тогда мы должны иметь выше  так как в противном случае линии и  будут пересекаться. По индукции  выше  для всех и аналогично для  . Но тогда любая строкаx 1 y 1 x 2 y 2 … x k y k x 1 x 2 x 1 y 2 y 1 x 1 y 1 x 2 y 2 x i + 1 x i i ∈ { 1 , … , k - 1 } y у к х 1$G$$x_1y_1x_2y_2\dots x_ky_kx_1$$x_2$$x_1$$y_2$$y_1$$x_1y_1$$x_2y_2$$x_{i+1}$$x_i$$i\in\{1, \dots, k-1\}$$y$$y_kx_1$должен либо оставить область между двумя столбцами вершин, либо пересечь все остальные ребра в цикле. Это противоречит нашему предположению, что граф имеет правильный рисунок. $\Box$

Лемма 3. Каждый подключенный не гусеница не в вашем классе.

Доказательство. Пусть связный граф, который не является гусеницей. Если он содержит цикл, его нет в вашем классе по лемме  , поэтому мы можем предположить, что это дерево. Если это не гусеница, она должна содержать вершину  с различными соседями , и  , каждый из которых имеет степень не менее   .2 x y 1 y 2 y 3$G$$2$$x$$y_1$$y_2$$y_3$$2$

Предположим, у нас есть рисунок  с требуемыми свойствами. Wlog,  выше  и  выше  . Пусть - сосед  . Ребро  должно пересекать или  , что противоречит нашему предположению о том, что граф имеет чертеж требуемой формы. $G$$y_2$$y_1$$y_3$$y_2$$z\neq x$$y_2$$y_2z$$xy_1$$xy_3$$\Box$

Теорема. Ваш класс графиков - это именно тот класс лесов, каждый из компонентов которого является гусеницей.

Доказательство. Пусть граф. Ясно, что  находится в вашем классе, если и только если каждый компонент: если какой-либо компонент не может быть нарисован как требуется, весь граф не может; если каждый компонент может быть нарисован так, как требуется, тогда весь граф можно нарисовать, расположив компоненты один над другим. Результат теперь следует из лемм и  . $G$$G$$1$$3$$\Box$

Следствие. Ваш класс графов - это класс графов, которые не имеют или подразделения  в качестве младшего.$K_3$$K_{1,3}$

Доказательство. Это препятствия для ширины пути $1$ . $\Box$

По сути, это препятствия, которые вы нашли: вам нужно а не потому что последний допустит в класс; подразделение является именно вашим вторым препятствием.$K_3$$K_4$$K_3$$K_{1,3}$

Итак, следующий ответ - это то, что я придумал:

Как вы уже упоминали, есть только два возможных случая, которые нельзя переставить.

Второй случай не правильное представление , если мы предположим , двудольный граф, так как Википедия определяет двудольный граф , как: каждое ребро соединяет вершину в единицы в V .$U$$V$

Изменить: я неправильно прочитал график, извините за это.

Это оставляет нас только с полным подграфом , что является условием, которого вы хотите избежать. И наоборот, достаточным условием является то, что ваш двудольный граф не имеет полного подграфа внутри себя.$K_{2,2}$

Чтобы доказать, что любой другой подграф действителен, вы можете представить следующее:

Сначала предположим, что у нас нет ребер, и начнем с произвольного ребра . Добавляя следующее ребро, мы имеем три возможных случая:$e$

Первый случай - у нас есть узел, который не начинается и не заканчивается в том же узле, что и первый ребро. Это оставляет нас без проблем, и мы можем продолжить вставку.

Второй случай - у нас есть ребро, которое на своем пути пересекает другое, уже существующее ребро. В этом случае мы должны поменять местами вершину или V 2 (с уже существующим ребром) с одним из новых ребер V 3 или V 4 , чтобы мы продолжали выполнять критерии.$V_1$$V_2$$V_3$$V_4$

Это предполагает, что у нас больше нет ребер, начинающихся или заканчивающихся в узлах, которые нужно поменять местами, что приводит нас к следующему третьему случаю: после замены одной из четырех вершин нам необходимо отследить все другие соединения из переставленной вершины ,$V1-V4$

Еще раз мы можем найти только три решения: либо мы отслеживаем конечное соединение, либо повторяем шаг, который мы уже сделали ранее (отслеживая все оставшиеся шаги). Если мы окажемся на конечном узле, мы можем поменять местами все отслеживаемые узлы.

Последний возможный случай приведет к узлу, который мы уже посетили, что оставит нас с полным подграфом, который мы затем можем привести к упомянутому условию .$K_{2,2}$

РЕДАКТИРОВАТЬ: Чтобы распространить это доказательство на второй случай, мы должны рассмотреть следующие условия:

В общем, если у нас есть подграф с хотя бы одним концентратором (3 или более соединений), это «довольно просто».

$\langle k\rangle > 1$

Поскольку я сам обладаю незначительными знаниями в этой области, но все же хочу предоставить вам возможное решение, я связал вас одной (надеюсь) соответствующей статьей

Если бы кто-нибудь назвал эту проблему, мне было бы интересно узнать, тем более, что я придумал это решение, только следуя соображениям из теоремы Фари и полным двудольным подграфам.