Толщина графа (Mklpnug ijgsg)

В теории графов толщина графа G — это наименьшее число плоских подграфов, на которые можно разложить рёбра графа G. То есть, если существует набор k плоских графов, имеющих одинаковый набор вершин, объединение которых даёт граф G, то толщина графа G не больше k.

Таким образом, плоский граф имеет толщину 1. Графы с толщиной 2 называются двупланарными графами. Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным. Задача эквивалентна определению, является ли полный граф K₉ бипланарным (он не бипланарен, так что гипотеза верна). Всесторонний обзор по теме толщины графа (по состоянию на 1998 год) написан Мутцелем, Оденталем и Шарбродтом.

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

Толщина полного графа с n вершинами, K_n, равна

$\left\lfloor {\frac {n+7}{6}}\right\rfloor ,$

за исключением случаев n = 9, 10, для которых толщина равна трём .

За исключением нескольких случаев, толщина полного двудольного графа K_a,b равна

$\left\lceil {\frac {ab}{2(a+b-2)}}\right\rceil .$

Связанные задачи

Любой лес планарен, а любой планарный граф можно разложить на три леса или меньше. Таким образом, толщина любого графа G не больше древесности того же графа (минимального числа лесов, на которые граф можно разложить) и не меньше древесности, делённой на три. Толщина графа G связана с другим стандартным инвариантом, вырожденностью, определяемой как максимум по всем подграфам графа G минимальной степени подграфа. Если граф с n вершинами имеет толщину t, то число его рёбер не превосходит t(3n − 6), откуда следует, что вырожденность не превосходит 6t − 1. С другой стороны, если вырожденность графа равна D, то его древесность и толщина не превосходит D.

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

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

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

Вычисление толщины заданного графа является NP-трудной, а проверка, что толщина не превосходит двух, является NP-полной задачей. Однако связь с древесностью позволяет аппроксимировать толщину с аппроксимационным коэффициентом 3 за полиномиальное время.

Литература

• David Eppstein. Towards a theory of geometric graphs. — Amer. Math. Soc., Providence, RI, 2004. — Т. 342. — (Contemp. Math). — doi:10.1090/conm/342/06132.
• Anthony Mansfield. Determining the thickness of graphs is NP-hard // Mathematical Proceedings of the Cambridge Philosophical Society. — 1983. — Т. 93, вып. 1. — doi:10.1017/S030500410006028X.
• W. T. Tutte. The thickness of a graph. — Indag. Math. — 1963. — Т. 25.
• Petra Mutzel, Thomas Odenthal, Mark Scharbrodt. The thickness of graphs: a survey // Graphs and Combinatorics. — 1998. — Т. 14, вып. 1. — doi:10.1007/PL00007219.
• Christian A. Duncan. On Graph Thickness, Geometric Thickness, and Separator Theorems // CCCG. — Vancouver, BC, 2009. — 17—19 August.
• Erkki Mäkinen, Timo Poranen. An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph // Missouri J. Math. Sci. — 2012. — Т. 24, вып. 1.
• В. Б. Алексеев, В. С. Гончаков. Толщина произвольного полного графа // Матем. сб. — 1976. — Т. 101(143), вып. 2(10).
• Peter Brass, Eowyn Cenek, Cristian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, Joseph S. B. Mitchell. On simultaneous planar graph embeddings // Computational Geometry. — 2007. — Т. 36, вып. 2. — doi:10.1016/j.comgeo.2006.05.006.
• Alice M. Dean, Joan P. Hutchinson, Edward R. Scheinerman. On the thickness and arboricity of a graph // Journal of Combinatorial Theory. — 1991. — Т. 52, вып. 1. — doi:10.1016/0095-8956(91)90100-X.
• Lowell W. Beineke, Frank Harary, John W. Moon. On the thickness of the complete bipartite graph // Proc. Cambridge Philos. Soc. — 1964. — Т. 60. — doi:10.1017/s0305004100037385.