Струнный граф

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

Бензер (Benzer 1959) описывал концепцию, близкую струнным графам, но для более общих структур. В этом контексте он также сформулировал специальный случай пересечения интервалов на прямой, ставший классическим классом интервальных графов. Позднее Синден (Sinden 1966) выразил ту же идеею для электрических сетей и печатных схем. Математическое изучение струнных графов началось со статьи Эрлиха, Ивена и Тарьяна (Ehrlich, Even, Tarjan 1976) и при содействии Синдена и Рональда Грэма описание струнных графов, в конечном счёте, было поставлено как открытая проблема на 5-м Венгерском коллоквиуме по комбинаторике в 1976^[1]. В конце концов, было доказано, что распознавание струнных графов является NP-полной задачей, откуда следует, что вряд ли существует простое описание этого класса^[2]

Любой планарный граф является струнным^[3] — можно образовать представление в виде струнного графа для любого вложенного в плоскость графа путём рисования для каждой вершины кривой, которая обходит по кругу вершину и середину каждого смежного ребра, как показано на рисунке. Для любого ребра uv графа, струны для u и v пересекаются дважды близ середины ребра uv, и не существует других пересечений, так что пересечение пары струн представляют смежные пары вершин исходного планарного графа. Альтернативно, по теореме об упаковке кругов, любой планарный граф может быть представлен в виде коллекции окружностей, любые две из которых пересекаются тогда и только тогда, когда соответствующие вершины смежны. Эти окружности (с начальной и конечной точкой, выбранными для превращения окружности в открытую кривую) дают представление заданного планарного графа в виде струнного графа. Чалопин, Гонсалвис и Ошан (Chalopin, Gonçalves, Ochem 2007) доказали, что любой планарный граф имеет представление в виде струнного графа, в котором каждая пара струн имеет максимум одно пересечение, а не так, как описано выше. Гипотеза Шейнермана, ныне доказанная, является даже более строгим утверждением, что любой планарный граф может быть представлен как граф пересечений отрезков.

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

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

Дополнение графа любого графа сравнимости является также струнным графом^[4].

Эрлих, Эвен и Тарьян (Ehrlich, Even, Tarjan 1976) показали, что вычисление хроматического числа струнного графа является NP-трудной задачей. Кратохвил (Kratochvil 1991a) обнаружил, что струнные графы образуют замкнутый класс порождённых миноров, но не минорно замкнутый класс графов.

Любой струнный граф с m рёбрами можно разбить на два подмножества, при этом каждое подмножество составляет фиксированную долю полного графа, путём удаления O(m^3/4log^1/2m) рёбер. Отсюда следует, что струнные графы без клик, струнные графы, не содержащие подграфов K_t,t ни для какой постоянной t, имеют O(n) рёбер и имеют полиномиальное расширение^[5][6].