Толщина графа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Tutte, 1963, с. 567—577.
2. Mutzel, Odenthal, Scharbrodt, 1998, с. 59—73.
3. Christian, 2009.
4. Алексеев, Гончаков, 1976, с. 212.
5. Mäkinen, Poranen, 2012, с. 76—87.
6. Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey Архивная копия от 3 марта 2016 на Wayback Machine
7. Mutzel, Odenthal, Scharbrodt, 1998.
8. Алексеев, Гончаков, 1976, с. 212—230.
9. Beineke, Harary, Moon, 1964, с. 1—5.
10. Dean, Hutchinson, Scheinerman, 1991, с. 147—151.
11. Brass и др., 2007, с. 117—130.
12. Eppstein, 2004, с. 75—86.
13. Mansfield, 1983, с. 9—23.

Литература

• 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.