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

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

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

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

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

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

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

Алгоритмы

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

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

Примечания

Литература

• H.-J. Bandelt, V. Chepoi, D. Eppstein. Combinatorics and geometry of finite and infinite squaregraphs // . — 2010. — Т. 24 , вып. 4 . — С. 1399—1440 . — doi : . — arXiv : .
• V. Chepoi, F. Dragan, Y. Vaxès. Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002). — 2002. — С. 346–355 .
• V. Chepoi, C. Fanciullini, Y. Vaxès. Median problem in some plane triangulations and quadrangulations // Comput. Geom.. — 2004. — Т. 27 , вып. 3 . — С. 193—210 . — doi : .
• I. Peterin. A characterization of planar median graphs // Discussiones Mathematicae Graph Theory. — 2006. — Т. 26 . — С. 41—48 . (недоступная ссылка)
• Солтан П. С., Замбицкий Д. К., Присакару К. Ф. Экстремальные задачи на графах и алгоритмы их решения. — Chişinǎu, Moldova: Штиинца, 1973.