Перечисление плоских графов ограниченной ширины дерева

Я ищу ссылки на следующую задачу: с учетом целых чисел и перечислить все неизоморфные плоские графы по вершинам и ширине дерева . Меня интересуют как теоретические, так и практические результаты, но в основном практические алгоритмы, которые можно кодировать и запускать для максимально больших значений и (подумайте, и ). Если у вас уже есть ответ, не обращайте внимания на сообщения ниже.$n$$k$$n$$\leq k$$n$$k$$k \leq 5$$n \leq 15$

Следующий подход работает нормально для перечисления всех неизоморфных графов по вершинам и ширине дерева (т.е. когда ограничение планарности сброшено):$n$$\leq k$

(a) Перечислите все неизоморфные графы по вершинам и ширине дерева .$n-1$$\leq k$

(b) Для каждой вершины на вершинах и ширине дерева , каждой клике на вершинах в и каждом подмножестве ребер в , сделайте из , добавив новую вершину примыкает к . Добавьте в список грахов по вершинам и ширине дерева .$G$$n-1$$\leq k$$C$$\leq k$$G$$S$$C$$G'$$G - S$$v$$C$$G'$${\cal L}$$n$$\leq k$

(c) Обрежьте , удалив копии того же графа.${\cal L}$

Заманчивый способ расширить это для перечисления плоских графов treewidth - просто отфильтровывать непланарные графы на каждой итерации. К сожалению, это не в состоянии генерировать все плоские графы с шириной дерева (например, потому что он перечисляет только вырожденные графы).$\leq k$$\leq k$$4$

Конечно, мы могли бы перечислить все графы по вершинам и ширине дерева и только затем отфильтровать неплоские, но это не позволяет использовать большинство графов неплоских и кажется очень неоптимальным.$n$$\leq k$

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

Для проверки того, меньше ли их ширина дерева, чем заданное значение , можно использовать эвристические алгоритмы для ускорения этого вычисления, только в том случае, если точные алгоритмы не практичны. например, в плоском графе сначала мы можем найти диаметр и соответствующий путь длины (который является диаметром). Тогда найти вершину , который имеет кратчайшее наибольшее расстояние ( ) в любую другую вершину среди всех вершин . Ширина дерева не более , если она меньше$k$$G$$G$$P$$d$$v\in P$$l$$u\in G\setminus P$$w\in P$$G$$d+l$$k$ тогда мы закончим, либо применяем некоторые другие эвристические алгоритмы, либо запускаем точный алгоритм.

Для менее чем трехсвязных графов также возможно применить эвристику путем нахождения вершин среза, а затем исправления этих вершин и определения ширины дерева оставшегося графа. Но так как число узлов мало ( ), если граф соединен, то диаметр не большой, и я думаю, что первая эвристика должна работать там. (Я не знаю, существует ли 5-ти связный плоский граф не более чем в 15 вершинах, но, как мы знаем, связного плоского графа не существует при )$15$$4$$t$$t>5$

Поскольку размер наибольшего обструкции для ширины дерева не известно , мы не можем просто угадать UpperBound значения древесной ширины данного графа . Но, похоже, что, по крайней мере, для плоских графов он не должен быть таким большим (нужно это доказать).$k$$G$

Можно перечислить все пары где - плоский граф с шириной трёх не более , - мешок размера такой, что существует дерево-разложение с в качестве пакета.$G,B$$G$$k$$B$$k$$G$$B$

Теперь для каждой пары где имеет вершин, мы строим новый граф для каждого подмножества в , добавляя вершину с качестве соседей, и пусть будет подмножеством размера из , Добавьте если плоско и не изоморфно любой паре, уже найденной.$G,B$$G$$n-1$$G'$$S$$B$$v$$S$$B'$$k$$B \cup v$$G',B'$$G'$

Простая верхняя граница количества записей, которое нужно сохранить, раз, сколько перечислимых графов, но это пессимистическая граница. Для большинства графиков ширины дерева k большинство подмножеств размера k не может содержать сумку, например, сетка имеет только возможных сумок.$n \choose k$$k \times n$$n \cdot 3^{k-1}$

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

Есть несколько приемов, которые можно применить, чтобы ускорить это, я бы посоветовал изучить: http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf