Нахождение двойственного графа

11

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

Вот моя проблема . Учитывая график , мне нужно найти другой граф G ' таких , что существует поверхность S и клеточное вложение G на S таких , что G ' является двойственным этим вложением G . Я знаю, что существует много возможных графов G ; Мне просто нужно найти для любого графа G .GGSGSGGGG

У меня есть несколько вопросов . Моя текущая стратегия состоит в том, чтобы (1) определить род в G , (2) найти вложение G на S n и (3) найти двойственное для этого вложения. Все эти шаги имеют известные алгоритмы (хотя (1) NP-Hard). Интересно, есть ли способ найти G , который обходит вычисления рода, поскольку это является узким местом этого подхода, и это мой первый вопрос. Мой второй вопрос: если я знаю, что G регулярна, может ли это облегчить вычисление рода? И мой третий вопрос - запрос на любые ссылки, которые могут помочь мне решить эту проблему.nGGSnGG

becko
источник
Я выкладываю подобный вопрос, требующий простой двойной граф здесь
becko

Ответы:

17

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

Мне нравится представление GEM (кодированная в графах карта) вложения из книги «Основы теории топологических графов» Беннингтона и Литтла. В этом представлении вложение представляется 3-реберным 3-регулярным графом с одним ребром для каждого флага вложения (падающая тройка вершины, ребра и грани) и одним ребром для каждых двух флагов, которые отличаются только один из элементов наборов вершин / ребер / граней, которые они представляют. Например, изображение ниже из Википедии может быть интерпретировано как GEM правильного додекаэдра, в котором красные циклы представляют его грани, желтые циклы представляют его ребра, а синие циклы представляют его вершины; края могут быть окрашены в соответствии с цветами их двух инцидентных граней.

большой ромбозидодекаэдр

При заданном круговом упорядочении ребер графа G его GEM можно найти, сделав цикл из 2d вершин для каждой вершины степени d в G, по два для каждого ребра, с парами вершин для каждого инцидентного ребра, встречающегося в цикл в выбранном круговом порядке, а затем для каждого ребра e из G, связывающего две пары ребер GEM для двух конечных точек e в прямоугольник. Если вы хотите ориентированное встраивание, выбор способа связывания этих четырех вершин в прямоугольник должен соответствовать круговым порядкам, в противном случае он может быть произвольным.

Тогда вершины, ребра и грани вложения G представлены циклами в GEM, которые чередуются между двумя из трех краевых цветов. Двойник G представлен GEM с тем же базовым 3-регулярным графом, но с двумя замененными краями. И граф, представленный GEM, может быть сформирован путем сжатия всех его циклов вершин и объединения пар параллельных ребер в одно ребро. Таким образом, построение дуала G (если вам все равно, какой дуал) может быть легко сделано за линейное время.

Дэвид Эппштейн
источник
1
На самом деле, дуал может быть «построен» из представления драгоценного камня за нулевое время, с помощью простого набора типов. Одна и та же структура данных представляет как исходную карту, так и двойственную.
Джефф
1
Также, чтобы «выбрать круговой порядок для ребер, инцидентных каждой вершине», я рекомендую использовать порядок в структуре данных списка смежности, которую вы используете для представления графа в любом случае.
Джефф
G
+1 Этот пост четко отвечает на вопрос, как я его сформулировал. Я не знаю, стоит ли пометить это как ответ прямо сейчас и начать новый пост с новой проблемой или изменить этот пост, поскольку проблема здесь явно в контексте.
becko
1
Вы знаете, сколько у вас вершин, ребер и граней, так что вы можете вычислить род по характеристике Эйлера (немного заботясь о том, ориентируется ли поверхность или нет).
Дэвид Эппштейн