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

У теорії графів товщина графа G — це найменша кількість плоских підграфів, на які можна розкласти ребра графа G. Тобто, якщо існує набір k плоских графів, які мають однаковий набір вершин, поєднання яких дає граф G, то товщина графа G не більше k.

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

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

Товщина повного графа з n вершинами, K_n, дорівнює

за винятком випадків n = 9, 10, для яких товщина дорівнює трьом.

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

Пов'язані задачі

Будь-який ліс є планарним, а будь-який планарний граф можна розкласти на три ліси або менше. Отже, товщина будь-якого графа G не більша від деревності того ж графа (найменшої кількості лісів, на які граф можна розкласти) і не менша від деревності, поділеної на 3. Товщина графа G пов'язана з іншим стандартним інваріантом, виродженістю, що визначається як максимум за всіма підграфами графа G найменшого степеня підграфа. Якщо граф з n вершинами має товщину t то число його ребер не перевищує t(3n − 6), звідки випливає, що виродженість не перевищує 6t − 1. З іншого боку, якщо виродженість графа дорівнює D, його деревність і товщина не перевищують D.

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

Інший інваріант графів — прямолінійна товщина або геометрична товщина графа G, підраховує найменшу кількість планарних графів, на які можна розкласти G з обмеженням, що їх можна намалювати одночасно за допомогою відрізків. Книжкова товщина (або товщина книги) додає обмеження, що всі вершини мають лежати на згині (корінці книги), формуючи колову схему графа. Однак, на відміну від деревності та виродженості, між цими величинами немає прямого зв'язку.

Обчислювальна складність

Обчислення товщини заданого графа є NP-складною, а перевірка, що товщина не перевищує двох, є NP-повною задачею. Однак, зв'язок із деревністю дозволяє апроксимувати товщину з апроксимаційним коефіцієнтом 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
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. — 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 (2 листопада).
• В. Б. Алексеев, В. С. Гончаков. Толщина произвольного полного графа // Матем. сб. — 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. — (Series B). — 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.