Струнный граф — это граф пересечений кривых на плоскости, каждая кривая при этом называется «струной». Если дан граф G, он является струнным тогда и только тогда, когда существует набор кривых (струн), нарисованных на плоскости, таких, что никакие три струны не пересекаются в одной точке и граф G изоморфен графу, вершины которого соответствуют кривым, а дуга в этом графе соответствует пересечению двух кривых.

Предпосылки Бензер описывал концепцию, близкую струнным графам, но для более общих структур. В этом контексте он также сформулировал специальный случай пересечения интервалов на прямой, ставший классическим классом интервальных графов. Позднее Синден выразил ту же идею для электрических сетей и печатных схем. Математическое изучение струнных графов началось со статьи Эрлиха, Ивена и Тарьяна , и при содействии Синдена и Рональда Грэма описание струнных графов, в конечном счёте, было поставлено как открытая проблема на 5-м Венгерском коллоквиуме по комбинаторике в 1976 г. В конце концов было доказано, что распознавание струнных графов является NP-полной задачей, откуда следует, что вряд ли существует простое описание этого класса.Кратохвил показал, что распознавание струнного графа является NP-трудной задачей, но не смог показать, что она может быть решена в классе NP. После промежуточных результатов Шефера и Стефанковича , Паха и Тота , Шефера, Седжвика и Стефанковича было завершено доказательство, что задача NP-полна.

Связанные классы графов Любой планарный граф является струнным Шефер и Стефанкович приписывают это наблюдение Синдену. — можно образовать представление в виде струнного графа для любого вложенного в плоскость графа путём рисования для каждой вершины кривой, которая обходит по кругу вершину и середину каждого смежного ребра, как показано на рисунке. Для любого ребра uv графа, струны для u и v пересекаются дважды близ середины ребра uv, и не существует других пересечений, так что пересечение пары струн представляют смежные пары вершин исходного планарного графа. Альтернативно, по теореме об упаковке кругов, любой планарный граф может быть представлен в виде коллекции окружностей, любые две из которых пересекаются тогда и только тогда, когда соответствующие вершины смежны. Эти окружности (с начальной и конечной точками, выбранными для превращения окружности в открытую кривую) дают представление заданного планарного графа в виде струнного графа. Чалопин, Гонсалвис и Ошан доказали, что любой планарный граф имеет представление в виде струнного графа, в котором каждая пара струн имеет максимум одно пересечение, а не так, как описано выше. Гипотеза Шейнермана, ныне доказанная, является даже более строгим утверждением, что любой планарный граф может быть представлен как граф пересечений отрезков.

Если все рёбра заданного графа G подразделяются, полученный граф является струнным графом тогда и только тогда, когда граф G планарен. В частности, подразделение полного графа K5, показанное на рисунке, струнным графом не является, поскольку K5 не планарен.

Любой круговой граф, как граф пересечений отрезков (хорд окружности), является также струнным графом. Любой хордальный граф может быть представлен как струнный граф — хордальные графы являются графами пересечений поддеревьев деревьев и можно образовать струнное представление хордального графа путём планарного вложения соответствующего дерева и заменой каждого поддерева струной, проходящей вокруг рёбер поддерева.

Дополнение графа любого графа сравнимости является также струнным графом; . См. также статью Фокса и Паха ..

Другие результаты Эрлих, Эвен и Тарьян показали, что вычисление хроматического числа струнного графа является NP-трудной задачей. Кратохвил обнаружил, что струнные графы образуют замкнутый класс порождённых миноров, но не минорно замкнутый класс графов.

Любой струнный граф с m рёбрами можно разбить на два подмножества, при этом каждое подмножество составляет фиксированную долю полного графа, путём удаления O(m3/4log1/2m) рёбер. Отсюда следует, что струнные графы без клик, струнные графы, не содержащие подграфов Kt,t ни для какой постоянной t, имеют O(n) рёбер и имеют полиномиальное расширение.

Примечания

Литература

Категория:Топологическая теория графов Категория:Графы пересечений Категория:NP-полные задачи