Ограничение числа ребер между звездными графами так, чтобы граф был плоским

У меня есть граф который состоит только из звездных графов. Звездный граф состоит из одного центрального узла, имеющего ребра для каждого другого узла в нем. Пусть быть разные звезды графики различных размеров , которые присутствуют в . Мы называем множество всех узлов , которые являются центрами в любом звезды граф .$G$$H_1, H_2, \ldots, H_n$$G$$R$

Теперь предположим, что эти звездные графы строят ребра для других звездных графов, так что между любыми узлами в нет ребер . Тогда, сколько существует ребер в максимуме между узлами в и узлами, которых нет в , если граф должен оставаться плоским?$R$$R$$R$

Я хочу верхнюю границу количества таких ребер. Одна верхней границы , что я имею в виде: рассматривать их как двудольный плоский граф , где представляет один набор вершин и отдых вершин образуют другой набор . Нас интересуют ребра между этими множествами ( и ). Так как это плоский двудольное, число таких ребер ограниченно удвоенное число узлов в .$R$$A$$R$$A$$G$

То , что я чувствую, что есть лучше связаны, может быть в два раза узлы плюс число узлов в .$A$$R$

Если вы можете опровергнуть мою интуицию, тогда это тоже будет хорошо. Надеюсь, некоторые из вас могут придумать хорошую оценку вместе с некоторыми соответствующими аргументами.

Ваше утверждение немного двусмысленно: сначала вы пишете, что «... таким образом, что между вершинами в нет инцидентных ребер », но следующий абзац подразумевает, что между вершинами в также нет ребер . Я также предполагаю, что звезды не пересекаются, и что вы считаете все края (включая те, которые изначально присутствовали в звездах). Предположим также, что есть как минимум две звезды, и хотя бы одна из них имеет степень .$R$$A$$\ge 2$

В этом случае вы не сможете ограничение ( = количество всех вершин). Рассмотрим немного другой сценарий: начните с любого набора из вершин, немного красного, черного, по крайней мере, двух каждого вида. На каждом шаге произвольно добавляйте ребро между красной и черной вершинами, если оно не создает пересечений или дублирующих ребер. Я утверждаю, что когда вы застряли, все циклы имеют длину .$2N-4$$N$$N$$4$

Ваш сценарий является частным случаем этого процесса, когда вы сначала создаете звезды, а затем добавляете оставшиеся ребра. Если все циклы имеют длину , следует ограничение . В более общем смысле, это показывает, что независимо от того, с какого двудольного графа вы начинаете, вы всегда можете дополнить его четырехугольным графом (словом, которое я составил).$4$$2N-4$

Теперь давайте покажем иск. В этом процессе все пути будут иметь чередующиеся черные и красные вершины, и каждый цикл будет иметь длину не менее$4$ . Если график не связан, вы можете соединить любую красную вершину на внешней грани одного компонента с черной вершиной на другой грани другого компонента. Таким образом, мы можем предположить, что граф уже связан.

Предположим, у вас есть лицо $F$ длины $6$ или больше. $F$должно иметь не менее трех черных вершин (возможно, равных). Если какая-то вершина$x$ повторяется на $F$Возьмите два по часовой стрелке $x$, сказать $x-a-...-x-b...$, $F$ должен содержать черную вершину $z\neq x$так, в зависимости от расположения $z$мы могли бы подключиться либо $a$ или $b$ в $z$ внутри $F$без дублирующих краев. Если вершина не повторяется, выберите отрезок по часовой стрелке$x-a-y-b-z$ из $F$, где $x,y,z$ черные и $a,b$красные. Если$x$ связан с $b$ тогда $a$ не может быть подключен к $z$ (по планарности), поэтому мы можем добавить один из ребер $(x,b)$, $(a,z)$ внутри $F$,