Рамочный граф

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

Рамочный граф.

Связанные классы графов

Рамочные графы включают в качестве специальных случаев деревья, решётки, шестерёнки и графы полимино.

Поскольку рамочные графы планарны, они также являются медианными, что означает, что для любых трёх вершин u, v и w существует единственная вершина m(u,v,w) (называемая медианой), которая лежит на кратчайшем пути между каждой парой этих трёх вершин^[1]. Как и в случае более общих медианных графов, рамочные графы являются частичными кубами — их вершины можно пометить битовыми строками таким образом, что расстояние Хэмминга между строками равно кратчайшему расстоянию между вершинами.

Характеристика

Шестерня с дополнительной вершиной — запрещённый подграф рамочных графов.

Рамочные графы можно охарактеризовать несколькими путями, отличными от свойства планарности^[2]:

• Они являются медианными графами, не содержащими в качестве порождённого подграфа любой член бесконечного семейства запрещённых графов. Эти запрещённые графы включают куб (симплекс-граф^[англ.] K₃), прямое произведение ребра и клешни K_1,3 (симплекс-граф клешни) и графы, образованные из шестерни добавлением дополнительной вершины, соединённой ребром с центром колеса.
• Они являются связными и двудольными графами такими, что если выбрать любую вершину r в качестве корня любая вершина имеет максимум два соседа, находящихся ближе к r, и такие, что для любой вершины v связка вершины v (граф, состоящий из вершин для каждого инцидентного v ребра и рёбер для всех циклов длины 4, содержащих вершину v) является либо циклом длины не менее трёх, либо несвязным набором путей.
• Они являются двойственными графами конфигураций прямых на гиперболической плоскости, в которых нет трёх попарно пересекающихся прямых.

Алгоритмы

Описание рамочных графов в терминах расстояния от корня и связок вершин (см. выше) можно использовать вместе с поиском в ширину как часть алгоритма с линейным временем работы для проверки, является ли данный граф рамочным без необходимости использовать более сложные алгоритмы с линейным временем работы для проверки планарности произвольных графов^[2].

Некоторые алгоритмические задачи на рамочных графах могут быть решены эффективнее, чем те же задачи для более общих планарных графов. Например, Чепой, Драган, Ваксес и Фансиллини^[3][4] предложили линейные по времени алгоритмы вычисления диаметра рамочных графов и для поиска вершины, которая находится на минимальном расстоянии до всех остальных вершин (то есть вершина, на которой достигается минимум максимального расстояния до всех остальных вершин).