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

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

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

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

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

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

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

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

Алгоритмы

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

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