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

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

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

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

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

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

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

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

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

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

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

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

Вычисление толщины заданного графа является NP-трудной, а проверка, что толщина не превосходит двух, является NP-полной задачей[13]. Однако связь с древесностью позволяет аппроксимировать толщину с аппроксимационным коэффициентом 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.