Помимо того, что квадратные графы являются планарными графами , они являются медианными графами , что означает, что для каждых трех вершин u , v и w существует уникальная медианная вершина m ( u , v , w ), которая лежит на кратчайших путях между каждой парой из трех вершин. [1] Как и в случае с медианными графами в более общем смысле, квадратные графы также являются частичными кубами : их вершины могут быть помечены двоичными строками таким образом, что расстояние Хэмминга между строками равно расстоянию кратчайшего пути между вершинами.
Граф, полученный из квадратного графа путем создания вершины для каждой зоны (класса эквивалентности параллельных ребер четырехугольников) и ребра для каждых двух зон, которые встречаются в четырехугольнике, является круговым графом , определяемым диаграммой хорд единичного круга , свободной от треугольников . [2]
Характеристика
Квадратные графы можно охарактеризовать несколькими способами, помимо их планарных вложений: [2]
Это медианные графы , которые не содержат в качестве индуцированного подграфа ни одного члена бесконечного семейства запрещённых графов . Эти запрещённые графы — куб ( симплексный граф K 3 ), декартово произведение ребра и клешни K 1,3 (симплексный граф клешни) и графы, образованные из графа шестерёнки путём добавления ещё одной вершины, соединённой со ступицей колеса (симплексный граф несвязного объединения цикла с изолированной вершиной).
Это графы, которые являются связными и двудольными , такими, что (если произвольная вершина r выбрана в качестве корня ) каждая вершина имеет не более двух соседей, более близких к r , и такими, что в каждой вершине v связь v (граф с вершиной для каждого ребра, инцидентного v, и ребром для каждого 4-цикла, содержащего v ) является либо циклом длины больше трех, либо несвязным объединением путей.
Характеристика квадратных графов с точки зрения расстояния от корня и связей вершин может использоваться вместе с поиском в ширину как часть линейного алгоритма времени для проверки того, является ли заданный граф квадратным графом, без необходимости использования более сложных линейных алгоритмов времени для проверки планарности произвольных графов. [2]
Некоторые алгоритмические задачи на квадратных графах могут быть вычислены более эффективно, чем в более общих планарных или медианных графах; например, Чепои, Драган и Ваксес (2002) и Чепои, Фанчуллини и Ваксес (2004) представляют линейные по времени алгоритмы для вычисления диаметра квадратных графов и для поиска вершины, минимизирующей максимальное расстояние до всех других вершин.
Примечания
^ Солтан, Замбицкий и Прискару (1973). См. Петерин (2006) для более общего обсуждения плоских медианных графиков.
^ abc Bandelt, Chepoi & Eppstein (2010).
Ссылки
Бандельт, Ханс-Юрген; Чепои, Виктор; Эппштейн, Дэвид (2010), «Комбинаторика и геометрия конечных и бесконечных квадратных графов», SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301, S2CID 10788524.
Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), «Проблема центра и диаметра в плоских четырех- и триангуляциях», Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002) , стр. 346–355.
Chepoi, Victor; Fanciullini, Clémentine; Vaxès, Yann (2004), «Проблема медианы в некоторых плоских триангуляциях и квадрангулях», Computational Geometry , 27 (3): 193–210, doi : 10.1016/j.comgeo.2003.11.002.
Петерин, Изток (2006), «Характеристика планарных медианных графов», Discussiones Mathematicae Graph Theory , 26 (1): 41–48, doi : 10.7151/dmgt.1299
Солтан, П.; Замбицкий Д.; Прискару, К. (1973), Экстремальные задачи на графах и алгоритмы их решения (на русском языке), Кишинев, Молдова: Ştiinţa.
