Планарное накрытие

Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия^[1].

Существование планарного накрытия является свойством, замкнутым относительно миноров^[2], а потому могут быть описаны конечным числом запрещённых миноров, но точный набор запрещённых миноров не известен. По тем же причинам существует алгоритм полиномиального времени для тестирования, имеет ли данный граф планарное накрытие, но явное описание этого алгоритма не известно.

Накрывающее отображение из одного графа C в другой граф H может быть описано функцией f из вершин C в вершины H, которая для каждой вершины v из C создаёт биекцию между окрестностью v и окрестностью f(v)^[3]. Если H является связным графом, каждая вершина H должна иметь одно и то же число вершин в прообразе C^[2]. Это число называется числом слоёв отображения, а C называется накрывающим графом графа G. Если и C, и H конечны, а C является планарным графом, C называется планарным накрытием графа H.

Граф правильного двенадцатигранника имеет симметрию, которая отображает каждую вершину в антиподальную вершину. Набор антиподальных пар вершин и их смежностей можно рассматривать также как граф, граф Петерсена. Двенадцатигранник образует планарное накрытие этого непланарного графа^[4]. Этот пример показывает, что не любой граф с планарным накрытием сам является планарным. Когда планарный граф накрывает непланарный, число слоёв должно быть чётным^[5][6].

Граф k-угольной призмы имеет 2k вершин и является планарным с двумя k-угольными гранями и k квадратными гранями. Если k = ab, ${\displaystyle a\geqslant 2}$ и ${\displaystyle b\geqslant 3}$, то граф имеет a-слойное накрывающее отображение в b-стороннюю призму, в которой две вершины k-призмы отображаются в одну и ту же вершину b-призмы, если они обе принадлежат одной и той же k-угольной грани и расстояние от одной до другой кратно b. Например, двенадцатиугольная призма^[англ.] может образовать 2-слойное накрытие шестиугольной призмы, 3-слойное накрытие куба или 4-слойное накрытие треугольной призмы. Эти примеры показывают, что граф может иметь много различных планарных накрытий, и могут быть планарным накрытием для многих графов. Кроме того, эти примеры показывают, что слой планарного накрытия может быть произвольно большим. Они не только накрывают призмы, например, шестиугольная призма может также накрывать непланарный коммунальный граф K_3,3 путём отождествления антиподальных пар вершин^[7].

Если граф H имеет планарное накрытие, то же верно для любого минора графа графа H^[2]. Минор G графа H может быть образован путём удаления рёбер и вершин из H и стягивания рёбер в H. Накрывающий граф C может быть преобразован тем же способом — для каждой удалённой вершины из H удаляем её прообраз в C, а для каждого стянутого ребра или вершины из H стягиваем их прообраз в C. Результат этих операций над C будет минором C, который накрывает G. Поскольку любой минор планарного графа сам является планарным, это даёт планарное накрытие минора графа G.

Поскольку графы с планарными накрытиями замкнуты относительно операции взятия миноров, из теоремы Робертсона — Сеймура следует, что их можно описать конечным набором запрещённых миноров^[8]. Граф является запрещённым минором для этого свойства, если он не имеет планарного накрытия, но все его миноры имеют планарные накрытия. Это описание может быть использовано для доказательства существования алгоритма полиномиального времени, который проверяет существование планарного накрытия путём поиска каждого запрещённого минора и возвращает «планарное накрытие существует», если этот поиск не найдёт ни одного из них^[9]. Однако, поскольку точный набор запрещённых миноров для этого свойства не известен, это доказательство существования не конструктивно и не ведёт к явному описанию множества запрещённых миноров или алгоритму, основанному на них^[10]

Другой операцией над графами, сохраняющей существование планарного накрытия, является преобразование звезда-треугольник, которое заменяет любую вершину степени три графа H на треугольник его трёх соседей^[2]. Однако обратное преобразование, преобразование треугольник-звезда, не обязательно сохраняет планарные накрытия.

Кроме того, дизъюнктное объединение двух графов, которые имеют накрытия, будут также иметь накрытие, образованное как дизъюнктное объединение накрывающих графов. Если два накрытия имеют те же слой, то он будет также слоем их объединения.

Нерешённые проблемы математики: Любой связный граф с планарным накрытием имеет вложение в проективную плоскость?

Если граф H имеет вложение в проективную плоскость, то оно обязательно имеет планарное накрытие, заданное прообразом H в ориентируемом двойном накрытии^[англ.] проективной плоскости, что есть сфера. Негами^[11] доказал обратное, что если связный граф H имеет двуслойное планарное накрытие, то H должен иметь вложение в проективную плоскость^[11][12]. Предположение, что H связан здесь необходимо, поскольку дизъюнктное объединение проективно планарных графов может не быть проективно-планарным^[13], но остаются имеющими планарное накрытие, дизъюнктное объединение ориентируемых двойных накрытий.

Регулярное накрытие графа H — это накрытие, получающееся из группы симметрий его накрывающего графа — прообразы каждой вершины из H составляют орбиту группы. Негами^[14] доказал, что любой связный граф с планарным регулярным накрытием может быть вложен в проективную плоскость^[14][15]. Основываясь на этих двух результатах, он высказал гипотезу, что на самом деле любой связный граф с планарным накрытием является проективным^[14][16]. На 2013 год гипотеза оставалась нерешённой ^[17]. Она известна также как «${\displaystyle 1-2-\infty }$ гипотеза Негами», поскольку её можно переформулировать как утверждение, что минимум слоёв планарного накрытия, если такое существует, должно быть либо 1, либо 2^[18].

Подобно графам с планарными накрытиями графы с вложениями в проективную плоскость могут быть описаны запрещёнными минорами. В этом случае точное множество запрещённых миноров известно, их 35. 32 из них связны и один из этих 32 графов обязательно появляется в качестве минора в любом связном непроективном планарном графе^[19][20]. Когда Негами высказал свою гипотезу, было доказано, что 31 из этих 32 запрещённых миноров либо не имеют планарных накрытий, либо могут быть сведены с помощью преобразования звезда-треугольник к более простым графам из этого списка^{[14][18][21][22] [23]}. Единственный оставшийся граф, для которого это ещё не сделано, это K_1,2,2,2, верхушечный граф с семью вершинами, который образует остов четырёхмерной восьмигранной пирамиды^[англ.]. Если показать, что K_1,2,2,2 не имеет планарных накрытий, это будет полным доказательством гипотезы. С другой стороны, если гипотеза не верна, K_1,2,2,2 будет минимальным контрпримером^[24].

Связанная гипотеза Майкла Феллоуза, уже решённая, касается планарных эмуляторов, обобщения планарных накрытий, когда отображаются окрестности графа сюръективно, а не биективно^[25][26][27]. Графы с планарными эмуляторами, подобно графам с планарными накрытиями, замкнуты относительно миноров и преобразований звезда-треугольник ^[28][29] В 1988 году независимо от Негами Феллоуз высказал гипотезу, что графы с планарными эмуляторами, это в точности графы, которые можно вложить в проективную плоскость^[30]. Гипотеза верна для регулярных эмуляторов, происходящих их автоморфизмов низлежащего накрывающего графа аналогично результату Негами ^[14] для регулярных планарных накрытий^[26]. Однако оказалось, что некоторые из 32 связных запрещённых миноров для проективно планарных графов имеют планарные эмуляторы^[31][32][17]. Поэтому гипотеза Феллоуза не верна. Нахождение полного набора запрещённых миноров для существования планарных эмуляторов остаётся открытой проблемой^[33].