Толщина (теория графов) - Thickness (graph theory)

В теория графов, то толщина графа грамм это минимальное количество планарные графы в который края грамм могут быть разделены. То есть, если существует набор k плоские графы, имеющие одинаковый набор вершин, такие что союз этих плоских графов грамм, то толщина грамм самое большее k.[1][2] Другими словами, толщина графа - это минимальное количество плоских подграфы чье объединение равно графу грамм.[3]

Таким образом, плоский граф имеет толщину 1. Графы толщиной 2 называются бипланарные графики. Концепция толщины берет начало в гипотезе 1962 г. Фрэнк Харари: Для любого графика из 9 точек, либо самого себя, либо его дополнительный граф является непланарный. Проблема эквивалентна определению того, полный график K9 является бипланарным (это не так, и гипотеза верна).[4] Комплексный[3] Обзор состояния дел в этой области на 1998 год был написан Петра Муцель, Томас Оденталь и Марк Шарбродт.[5]

Конкретные графики

Толщина полный график на п вершины, Kп, является

кроме тех случаев, когда п = 9, 10 для которых толщина равна трем.[6][7]

За некоторыми исключениями толщина полный двудольный граф Kа, б обычно:[8][9]

Связанные проблемы

Каждый лес является плоским, и каждый плоский граф может быть разбит не более чем на три леса. Следовательно, толщина любого графика грамм не больше, чем родословие одного и того же графа (минимальное количество лесов, на которые он может быть разбит) и по крайней мере равной древесности, деленной на три.[2][10] Толщина грамм также находится в пределах постоянных коэффициентов другого стандарта инвариант графа, то вырождение, определяемый как максимум, по подграфам грамм, минимальной степени в подграфе. Если п-вершинный граф имеет толщину т тогда в нем обязательно должно быть не более т(3п − 6) рёбер, откуда следует, что его вырождение не превосходит 6т − 1. В обратном направлении, если граф имеет вырождение D то он имеет древовидность и толщину, не более D.

Толщина тесно связана с проблемой одновременное встраивание.[11] Если два или более плоских графа имеют один и тот же набор вершин, то можно встроить все эти графы в плоскость с ребрами, нарисованными как кривые, так, чтобы каждая вершина имела одинаковое положение на всех различных чертежах. Однако может оказаться невозможным построить такой рисунок, сохраняя при этом края, нарисованные прямыми. отрезки линии.

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

Вычислительная сложность

это NP-жесткий для вычисления толщины данного графа, и НП-полный чтобы проверить, не превышает ли толщина двух.[13] Однако связь с древовидностью позволяет приблизить толщину с точностью до коэффициент аппроксимации из 3 дюймов полиномиальное время.

Рекомендации

  1. ^ Тутте, В. Т. (1963), «Толщина графика», Indag. Математика., 25: 567–577, МИСТЕР  0157372.
  2. ^ а б Муцель, Петра; Оденталь, Томас; Шарбродт, Марк (1998), "Толщина графиков: обзор", Графы и комбинаторика, 14 (1): 59–73, Дои:10.1007 / PL00007219, МИСТЕР  1617664.
  3. ^ а б Кристиан А. Дункан, О толщине графа, геометрической толщине и теоремах о разделителях, CCCG 2009, Ванкувер, Британская Колумбия, 17–19 августа 2009 г.
  4. ^ Мякинен, Эркки; Поранен, Тимо (2012). «Аннотированная библиография по толщине, внешней толщине и древовидности графа». Миссури Дж. Математика. Наука. 24 (1): 76–87.
  5. ^ Петра Муцель, Томас Оденталь и Марк Шарбродт, Толщина графиков: обзор
  6. ^ Муцель, Оденталь и Шарбродт (1998), Теорема 3.2.
  7. ^ Алексеев, В.Б .; Гончаков, В. С. (1976), "Толщина произвольного полного графа", Мат. Сб. (Н.С.), 101 (143): 212–230, МИСТЕР  0460162.
  8. ^ Муцель, Оденталь и Шарбродт (1998), Теорема 3.4.
  9. ^ Бейнеке, Лоуэлл В.; Харари, Фрэнк; Луна, Джон В. (1964), "О толщине полного двудольного графа", Proc. Cambridge Philos. Soc., 60: 1–5, Дои:10,1017 / с0305004100037385, МИСТЕР  0158388.
  10. ^ Дин, Алиса М .; Хатчинсон, Джоан П.; Шайнерман, Эдвард Р. (1991), «О толщине и древовидности графика», Журнал комбинаторной теории, Серия B, 52 (1): 147–151, Дои:10.1016 / 0095-8956 (91) 90100-Х, МИСТЕР  1109429.
  11. ^ Брасс, Питер; Cenek, Eowyn; Дункан, Кристиан А .; Эфрат, Алон; Эртен, Цесим; Ismailescu, Dan P .; Кобуров, Стивен Г .; Любив, Анна; Митчелл, Джозеф С. Б. (2007), «Об одновременных вложениях плоских графов», Вычислительная геометрия, 36 (2): 117–130, Дои:10.1016 / j.comgeo.2006.05.006, МИСТЕР  2278011.
  12. ^ Эппштейн, Дэвид (2004), «Разделение толщины от геометрической толщины», К теории геометрических графов, Contemp. Математика, 342, Амер. Математика. Soc., Providence, RI, стр. 75–86, arXiv:математика / 0204252, Дои:10.1090 / conm / 342/06132, МИСТЕР  2065254.
  13. ^ Мэнсфилд, Энтони (1983), "Определение толщины графиков NP-сложно", Математические труды Кембриджского философского общества, 93 (1): 9–23, Дои:10.1017 / S030500410006028X, МИСТЕР  0684270.