В полиэдральной комбинаторике , разделе математики, теорема Стейница представляет собой характеристику неориентированных графов, образованных ребрами и вершинами трехмерных выпуклых многогранников : они в точности являются ( простыми ) 3-вершинно-связными планарными графами (по крайней мере, с четырьмя вершины). То есть каждый выпуклый многогранник образует 3-связный плоский граф, и каждый 3-связный плоский граф может быть представлен как график выпуклого многогранника. По этой причине трехсвязные плоские графы также известны как многогранные графы . [1] Бранко Грюнбаумназвал эту теорему «наиболее важным и глубоким известным результатом о 3-многогранниках ». [2]
Теорема появляется в статье Эрнста Стейница 1922 года , в честь которого она названа. Это можно доказать с помощью математической индукции (как это сделал Стейниц), найдя состояние с минимальной энергией двумерной пружинной системы и перенеся результат в три измерения, или используя теорему об упаковке кругов . Известно несколько расширений теоремы, в которых многогранник, реализующий данный граф, имеет дополнительные ограничения; например, каждый многогранный граф является графиком выпуклого многогранника с целыми координатами или графиком выпуклого многогранника, все ребра которого касаются общей средней сферы .
В более высоких измерениях проблема описания графиков выпуклых многогранников остается открытой.
Определения и формулировка теоремы.
Неориентированный граф представляет собой систему вершин и ребер , каждое ребро , соединяющее две вершины. Из любого многогранника можно образовать граф, если сопоставить вершины графа с вершинами многогранника и соединить любые две вершины графа ребром, если соответствующие две вершины многогранника являются концами ребра многогранника. Этот граф известен как скелет многогранника. [3]
Граф является плоским, если его вершины можно нарисовать как точки на евклидовой плоскости , а его ребра - как кривые, соединяющие эти точки, так что никакие две реберные кривые не пересекаются друг с другом и так, что точка, представляющая вершину, лежит на кривой представляет ребро только тогда, когда вершина является конечной точкой ребра. По теореме Фари достаточно рассматривать только плоские чертежи, на которых кривые, представляющие края, являются отрезками прямых . Граф является 3-связным, если после удаления любых двух его вершин любая другая пара вершин остается соединенной путем. Теорема Стейница утверждает, что эти два условия необходимы и достаточны для характеристики скелетов трехмерных выпуклых многогранников: данный граф G является графиком выпуклого трехмерного многогранника тогда и только тогда, когда G плоский и 3-вершинный- связанный. [2] [4]
История и нейминг
Теорема Стейница названа в честь Эрнста Стейница , который представил свое первое доказательство для публикации в 1916 году [5].
Название «теорема Стейница» применялось и к другим результатам Стейница:
- обмен лемма Штейниц подразумевая , что каждый базис векторного пространства имеет одинаковое число векторов, [6]
- теорема о том, что если выпуклая оболочка точечного множества содержит единичную сферу, то выпуклая оболочка конечного подмножества точки содержит меньшую концентрическую сферу, [7] и
- Векторное обобщение Стейница теоремы о рядах Римана о перестановках условно сходящихся рядов . [8] [9] [10] [11]
Доказательства
Одно из направлений теоремы Стейница (более легкое для доказательства) утверждает, что график каждого выпуклого многогранника является плоским и 3-связным. Как показано на рисунке, планарность может быть продемонстрирована с помощью диаграммы Шлегеля : если поместить источник света около одной стороны многогранника и плоскость на другой стороне, тени от краев многогранника образуют плоский граф, вложенный таким образом, чтобы края были отрезками прямых линий. 3-связность многогранного графа является частным случаем теоремы Балински о том, что граф любого k -мерного выпуклого многогранника является k- связным. [12]
Другое, более сложное направление теоремы Стейница утверждает, что каждый плоский 3-связный граф является графиком выпуклого многогранника. Для этой части есть три стандартных подхода: доказательства по индукции, перевод двумерных вложений Тутте в три измерения с использованием соответствия Максвелла – Кремоны и методы, использующие теорему об упаковке кругов для создания канонического многогранника .
Индукция
Первоначальное доказательство Стейница включало поиск последовательности преобразований Δ-Y и Y-Δ, которые сводят любой трехсвязный планарный граф к K 4 , графу тетраэдра. Преобразование Y-Δ удаляет вершину третьей степени из графа, добавляя ребра между всеми ее бывшими соседями, если эти ребра еще не существовали; обратное преобразование, преобразование Δ-Y, удаляет ребра треугольника из графа и заменяет их новой вершиной третьей степени, смежной с теми же тремя вершинами. Как только такая последовательность найдена, ее можно перевернуть и преобразовать в геометрические операции, которые шаг за шагом строят желаемый многогранник, начиная с тетраэдра. Каждое преобразование Y-Δ в обратной последовательности может быть выполнено геометрически путем отсечения вершины третьей степени от многогранника. Преобразование Δ-Y в обратной последовательности можно выполнить геометрически, удалив треугольную грань многогранника и расширив его соседние грани до точки, где они встречаются, но только тогда, когда точка тройного пересечения трех соседних граней находится на дальней стороне. удаленной грани многогранника. Когда точка тройного пересечения находится не на дальней стороне этой грани, достаточно проективного преобразования многогранника, чтобы переместить его на правильную сторону. Следовательно, индукцией по количеству преобразований Δ-Y и Y-Δ, необходимых для сведения данного графа к K 4 , любой многогранный граф может быть реализован как многогранник. [5]
Более поздняя работа Епифанова усилила доказательство Стейница, что любой многогранный граф может быть приведен к K 4 с помощью Δ-Y и Y-Δ преобразований. Епифанов доказал, что если в плоском графе заданы две вершины, то граф можно свести к единственному ребру между этими терминалами, комбинируя преобразования Δ-Y и Y-Δ с последовательно-параллельными редукциями . [13] Доказательство Епифанова было сложным и неконструктивным, но Трумпер упростил его, используя методы, основанные на минорах графов . Трумпер заметил, что каждый сеточный граф сводится с помощью Δ-Y и Y-Δ преобразований таким образом, что эта сводимость сохраняется с помощью миноров графа и что каждый плоский граф является минором сеточного графа. [14] Эту идею можно использовать для замены леммы Стейница о существовании редукционной последовательности. После этой замены остальная часть доказательства может быть проведена с использованием индукции так же, как и в исходном доказательстве Стейница. [4] Для этих доказательств, проводимых с использованием любого из способов нахождения последовательностей преобразований Δ-Y и Y-Δ, существуют многогранные графы, требующие нелинейного числа шагов. Точнее, иногда необходимо Ω ( n 3/2 ) шагов, а наиболее известная верхняя граница количества шагов еще хуже, O ( n 2 ). [15]
Альтернативная форма доказательства индукции основана на удалении ребер (и сжатии вершин степени два, которые могут быть выполнены этим удалением) или сжатии ребер и формировании минора данного плоского графа. Любой многогранный граф может быть уменьшен до K 4 линейным числом этих операций, и снова операции могут быть обращены, а обратные операции выполнены геометрически, давая многогранную реализацию графа. Однако, хотя проще доказать, что для этого типа аргумента существует редукционная последовательность, а редукционные последовательности короче, геометрические шаги, необходимые для обращения последовательности, более сложны. [16]
Подъем
Если граф нарисован на плоскости с прямыми краями, то равновесное напряжение определяется как присвоение ребрам ненулевых действительных чисел (весов) с тем свойством, что каждая вершина находится в положении, заданном взвешенной суммой своих соседи. Согласно соответствию Максвелла – Кремоны, равновесное напряжение может быть поднято до кусочно-линейной непрерывной трехмерной поверхности, так что края, образующие границы между плоскими частями поверхности, выступают на данный чертеж. Вес и длина каждого ребра определяют разницу в уклонах поверхности по обе стороны от ребра, а условие, что каждая вершина находится в равновесии со своими соседями, эквивалентно условию, что эти различия уклонов заставляют поверхность встречаться с сам правильно в окрестности вершины. Положительные веса переводятся в выпуклые двугранные углы между двумя гранями кусочно-линейной поверхности, а отрицательные веса переводятся в вогнутые двугранные углы. И наоборот, каждая непрерывная кусочно-линейная поверхность возникает таким образом из равновесного напряжения. Если нарисован конечный планарный граф и задано равновесное напряжение таким образом, что все внутренние ребра чертежа имеют положительный вес, а все внешние ребра имеют отрицательный вес, то, преобразовав это напряжение в трехмерную поверхность таким образом, а затем заменяя плоскую поверхность, представляющую внешность графа, его дополнением в той же плоскости, получаем выпуклый многогранник с дополнительным свойством, что его перпендикулярная проекция на плоскость не имеет пересечений. [17] [18]
Соответствие Максвелла – Кремоны использовалось для получения полиэдральных реализаций многогранных графов путем комбинирования его с методом рисования плоских графов У. Т. Тутта , вложением Тутта . Метод Тутте начинается с фиксации одной грани многогранного графа в выпуклом положении на плоскости. Эта грань станет внешней гранью рисунка графика. Метод продолжается установкой системы линейных уравнений в координатах вершины, согласно которой каждая оставшаяся вершина должна быть помещена в среднее значение своих соседей. Тогда, как показал Тутте, эта система уравнений будет иметь единственное решение, в котором каждая грань графа изображена как выпуклый многоугольник. [19] В результате получается почти равновесное напряжение: если каждому внутреннему ребру присвоить вес, равный единице, то каждая внутренняя вершина чертежа находится в равновесии. Однако не всегда можно присвоить отрицательные числа внешним краям, чтобы они тоже находились в равновесии. Такое присвоение всегда возможно, когда внешняя грань является треугольником, поэтому этот метод можно использовать для реализации любого многогранного графа, имеющего треугольную грань. Если многогранный граф не содержит треугольной грани, его дуальный граф действительно содержит треугольник, а также является многогранным, поэтому можно реализовать двойственный таким образом, а затем реализовать исходный граф как полярный многогранник двойственной реализации. [20] [21] Также возможно реализовать любой многогранный граф напрямую, выбрав внешней гранью любую грань с не более чем пятью вершинами (что существует во всех многогранных графах) и более тщательно выбрав фиксированную форму этой грани в таким образом, чтобы вложение Тутте можно было поднять, [22] или используя инкрементный метод вместо метода Тутте, чтобы найти поднимаемый плоский чертеж, который не имеет равных весов для всех внутренних краев. [23]
Упаковка круга
Согласно одному из вариантов теоремы об упаковке кругов , для каждого многогранного графа и двойственного к нему графа существует система кругов на плоскости или на любой сфере, представляющая вершины обоих графов, так что две соседние вершины в одном и том же графе равны представлены касательными окружностями , прямая и двойственная вершины, которые представляют вершину и грань, которые касаются друг друга, представлены ортогональными окружностями, а все остальные пары окружностей не пересекаются. [24] Из такого представления на сфере можно найти полиэдральную реализацию данного графа как пересечение набора полупространств, по одному для каждой окружности, представляющей дуальную вершину, с границей полупространства, содержащего окружность. Альтернативно и эквивалентно, можно найти тот же многогранник, что и выпуклая оболочка набора точек (его вершин), такой, что горизонт, видимый при просмотре сферы из любой вершины, равен кругу, соответствующему этой вершине. Сфера становится срединной сферой реализации: каждое ребро многогранника касается его в точке, где встречаются две касательные прямые окружности и две двойственные окружности, ортогональные первичным окружностям и касательные друг к другу. [25]
Реализации с дополнительными свойствами
Целочисленные координаты
Можно доказать более сильную форму теоремы Стейница, что любой многогранный граф может быть реализован выпуклым многогранником, для которого все координаты вершин являются целыми числами. Например, оригинальное доказательство Стейница, основанное на индукции, может быть усилено таким образом. Однако целые числа, которые могут быть получены в результате этой конструкции, имеют двойную экспоненциальную зависимость от числа вершин данного многогранного графа. Запись чисел такой величины в двоичной системе счисления потребует экспоненциального числа битов. [26]
Последующие исследователи нашли алгоритмы реализации на основе подъема, которые используют только O ( n ) бит на вершину. [22] [27] Также можно ослабить требование, чтобы координаты были целыми числами, и назначить координаты таким образом, чтобы координаты x вершин были различными целыми числами в диапазоне [0,2 n - 4] и две другие координаты являются действительными числами в диапазоне [0,1], так что каждое ребро имеет длину не менее единицы, в то время как весь многогранник имеет объем O ( n ). [28] Известно, что некоторые многогранные графы реализуемы на сетках только полиномиального размера; в частности, это верно для пирамид (реализации графов-колес ), призм (реализации графов-призм ) и многогранников с накоплением (реализации аполлонических сетей ). [29]
Равные склоны
Халин график представляет собой плоский граф , образованный из плоского встраиваемого дерева (без градусоден двух вершин) путем соединения листьев дерева в циклю . Каждый граф Халина может быть реализован многогранником, в котором этот цикл образует горизонтальную базовую грань, каждая другая грань лежит непосредственно над базовой гранью (как в многогранниках, реализованных посредством подъема), и каждая грань имеет одинаковый наклон. Эквивалентно прямой скелет базовой грани комбинаторно эквивалентен дереву, из которого был сформирован граф Халина. Доказательство этого результата использует индукцию: любое корневое дерево может быть уменьшено до меньшего дерева, удалив листья из внутреннего узла, все дочерние элементы которого являются листьями, граф Халина, сформированный из меньшего дерева, имеет реализацию по предположению индукции, и это можно изменить эту реализацию, чтобы добавить любое количество дочерних листьев к узлу дерева, дочерние элементы которого были удалены. [30]
Определение формы лица
В любом многограннике, представляющем данный многогранный граф G , грани G - это в точности циклы в G, которые не разделяют G на две компоненты: то есть удаление лицевого цикла из G оставляет остальную часть G в виде связного подграфа. Таким образом, комбинаторная структура граней (но не их геометрическая форма) однозначно определяется из структуры графа. Другое усиление теоремы Стейница, сделанное Барнеттом и Грюнбаумом, утверждает, что для любого многогранного графа, любой грани графа и любого выпуклого многоугольника, представляющего эту грань, можно найти многогранную реализацию всего графа, которая имеет заданную форму для обозначенное лицо. Это связано с теоремой Тутте, что любой многогранный граф можно нарисовать на плоскости со всеми выпуклыми гранями и любой заданной формой для его внешней грани. Однако чертежи плоских графов, полученные методом Тутте, не обязательно поднимаются до выпуклых многогранников. Вместо этого Барнетт и Грюнбаум доказывают этот результат, используя индуктивный метод [31]. Также всегда возможно, учитывая многогранный граф G и произвольный цикл C в G , найти реализацию, для которой C образует силуэт реализации при параллельной проекции . [32]
Касательные сферы
Теорема Кебе- Андреева- Терстона об упаковке кругов может быть интерпретирована как еще одно усиление теоремы Стейница, согласно которой каждый трехсвязный плоский граф может быть представлен как выпуклый многогранник таким образом, что все его ребра касаются одной и той же единичной сферы. . [25] Выполняя тщательно подобранное преобразование Мёбиуса упаковки кругов перед преобразованием ее в многогранник, можно найти полиэдральную реализацию, которая реализует все симметрии основного графа в том смысле, что каждый автоморфизм графа является симметрией многогранная реализация. [33] [34] В более общем смысле , если G является многогранными графами и К является любым гладким трехмерное телом выпуклого , можно найти многогранное представление G , в которой все ребра являются касательной к K . [35]
Методы упаковки Круга также могут быть использованы для характеристики графов многогранников , которые имеют circumsphere или insphere . Характеристика включает веса ребер, ограниченные системами линейных неравенств. Эти веса соответствуют углам, образованным соседними окружностями в системе окружностей, образованных пересечениями граней многогранника с их описанной сферой или горизонтами вершин многогранника на его внутренней сфере. [36] [37]
Связанные результаты
В любой размерности больше трех алгоритмическая проблема Стейница состоит в том, чтобы определить, является ли данная решетка решеткой граней выпуклого многогранника . Это завершено для экзистенциальной теории действительных чисел теоремой универсальности Рихтера-Геберта. [38] Однако, поскольку данный граф может соответствовать более чем одной решетке граней, трудно распространить этот результат о полноте на проблему распознавания графов 4-многогранников, и сложность этой проблемы остается открытой. [39]
Исследователи также нашли теоретико-графические характеристики графиков некоторых специальных классов трехмерных невыпуклых многогранников [40] [41] и четырехмерных выпуклых многогранников. [39] [42] [43] Однако в обоих случаях общая проблема остается нерешенной. В самом деле, даже проблема определения того, какие полные графы являются графами невыпуклых многогранников (кроме K 4 для тетраэдра и K 7 для многогранника Часара ), остается нерешенной. [44]
Ласло Ловас показал соответствие между полиэдральными представлениями графов и матрицами, реализующими графовые инварианты Колена де Вердьера одних и тех же графов. [45]
Рекомендации
- ^ Вайсштейн, Эрик В. , "Многогранный граф" , MathWorld
- ^ а б Грюнбаум, Бранко (2003), "13.1 Теорема Стейница", Выпуклые многогранники , Тексты для выпускников по математике, 221 (2-е изд.), Springer-Verlag, стр. 235–244, ISBN 0-387-40409-0
- ^ С технической точки зрения, этот график представляет собой 1-скелет; см. Grünbaum (2003) , стр. 138, и Зиглер (1995) , стр. 64.
- ^ а б Зиглер, Гюнтер М. (1995), "Глава 4: Теорема Стейница для 3-многогранников", Лекции по многогранникам , Тексты для выпускников по математике, 152 , Springer-Verlag, стр. 103–126, ISBN 0-387-94365-X
- ^ а б Стейниц, Эрнст (1922), «Polyeder und Raumeinteilungen» , Encyclopädie der Mathematischen Wissenschaften , Band 3 (Geometries) , стр. 1–139,
Abgeschlossen am 31. августа 1916 г.
- ^ Зинель, Мариуш (1996), "Теорема Стейница и размерность векторного пространства", Формализованная математика , 5 (8): 423–428, CiteSeerX 10.1.1.79.1707
- ^ Киркпатрик, Дэвид ; Мишра, Бхубанешвар; Яп, Чи-Кенг (1992), "Количественные теоремы Стейница с приложениями к многоязычному схватыванию", Дискретная и вычислительная геометрия , 7 (1): 295–318, doi : 10.1007 / BF02187843
- ^ Rosenthal, Питер (1987), "Замечательное теорема Леви и Стейница", Американский Математический Месячный , 94 (4): 342-351, DOI : 10,2307 / 2323094 , JSTOR 2323094
- ^ Banaszczyk, Wojciech (1991), "Глава 3.10 Теорема Леви-Стейница", Аддитивные подгруппы топологических векторных пространств , Лекции по математике, 1466 , Берлин: Springer-Verlag, стр. Viii + 178, ISBN 3-540-53917-4, Руководство по ремонту 1119302
- ^ Кадец ВМ; Кадец М.И. (1991), "Глава 6 Теорема Стейница и B- выпуклость", Перестановки рядов в банаховых пространствах , Переводы математических монографий, 86 (Перевод Гарольда Х. Макфадена с русского языка (Тарту), 1988 изд. ), Провиденс, Род-Айленд: Американское математическое общество, стр. Iv + 123, ISBN. 0-8218-4546-2, Руководство по ремонту 1108619
- ^ Кадец Михаил И .; Кадец, Владимир М. (1997), "Глава 2.1 Теорема Стейница о диапазоне сумм ряда, Глава 7 Теорема Стейница и B- выпуклость", Ряды в банаховых пространствах: условная и безусловная сходимость , Теория операторов: достижения и приложения, 94 (Перевод Андрея Якоба из русскоязычного ред.), Базель: Birkhäuser Verlag, стр. Viii + 156, ISBN 3-7643-5401-1, Руководство по ремонту 1442255
- ^ Balinski, М. Л. (1961), "О структуре графа выпуклых многогранников в п - пространстве" , Тихоокеанский журнал математики , 11 (2): 431-434, DOI : 10,2140 / pjm.1961.11.431 , МР 0126765
- ^ Епифанов, Г.В. (1966), "Приведение плоского графа к ребру преобразованиями звезда-треугольник", Доклады АН СССР , 166 : 19–22, MR 0201337.
- ^ Truemper, К. (1989), "О приведении дельта-Уай для плоских графов", Журнал теории графов , 13 (2): 141-148, DOI : 10.1002 / jgt.3190130202 , МР 0994737
- ^ Чанг, Сянь-Чжи; Коссарини, Маркос; Эриксон, Джефф (2019), «Нижние оценки электрического сокращения на поверхностях», в Барекет, Гилл; Ван, Юсу (ред.), 35-й Международный симпозиум по вычислительной геометрии (SoCG 2019) , Leibniz International Proceedings in Informatics (LIPIcs), 129 , Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, стр. 25: 1–25 : 16, arXiv : 1707.04683 , doi : 10.4230 / LIPIcs.SoCG.2019.25 , ISBN 978-3-95977-104-7, Руководство по ремонту 3968611
- ^ Барнетт, Дэвид В .; Грюнбаум, Бранко (1969), "О теореме Стейница о выпуклых 3-многогранниках и о некоторых свойствах плоских графов", Многогранность теории графов (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Springer, pp. 27–40, MR 0250916.
- ^ Максвелл, Дж. Клерк (1864), «О взаимных фигурах и диаграммах сил», Philosophical Magazine , 4-я серия, 27 : 250–261
- ^ Уайтли, Уолтер (1982), "Движения и напряжения спроецированных многогранников", Структурная топология , 7 : 13–38, MR 0721947
- ^ Tutte, WT (1963), "Как нарисовать график", Труды Лондонского математического общества , 13 : 743-767, DOI : 10.1112 / ПНИЛ / s3-13.1.743 , MR 0158387
- ^ Онн, Шмуэль; Штурмфельс, Бернд (1994), "Количественная теорема Стейница", Beiträge zur Algebra und Geometrie , 35 (1): 125–129, MR 1287206
- ^ Идс, Питер ; Гарван, Патрик (1996), «Рисование напряженных плоских графов в трех измерениях», Graph Drawing (GD '95) , Lecture Notes in Computer Science , 1027 , Springer, pp. 212–223, doi : 10.1007 / bfb0021805
- ^ а б Рибо Мор, Арес; Роте, Гюнтер; Шульц, Андре (2011), "Малая Сетка вложения 3-многогранники", Дискретная & Вычислительная геометрия , 45 (1): 65-87, Arxiv : 0908,0488 , DOI : 10.1007 / s00454-010-9301-0 , S2CID 10141034
- ^ Хробак, Марек; Гудрич, Майкл Т .; Tamassia, Роберто (1996), "Выпуклые рисунки графов в двух и трех измерениях", Труды 12 - го ACM симпозиум по вычислительной геометрии (SoCG '96) , АСМ, стр 319-328,. DOI : 10,1145 / 237218,237401 , S2CID 1015103
- ^ Brightwell, Graham R .; Scheinerman, Эдвард Р. (1993), "Представление плоских графов", SIAM журнал по дискретной математике , 6 (2): 214-229, DOI : 10,1137 / 0406017
- ^ а б Зиглер, Гюнтер М. (2007), «Выпуклые многогранники: экстремальные конструкции и формы f -векторов. Раздел 1.3: Теорема Стейница через упаковки кругов», Миллер, Эзра; Райнер, Виктор; Штурмфельс, Бернд (ред.), Геометрическая комбинаторика , IAS / Park City Mathematics Series, 13 , Американское математическое общество , стр. 628–642, ISBN 978-0-8218-3736-8
- ^ Венкатасубраманян, Суреш (2006), Планарные графы и теорема Стейница
- ^ Бучин, Кевин; Шульц, Андре (2010), «О количестве остовных деревьев, которые может иметь планарный граф», Алгоритмы - 18-й ежегодный европейский симпозиум (ESA 2010) , Lecture Notes in Computer Science, 6346 , Springer-Verlag, pp. 110–121, Bibcode : 2010LNCS.6346 ..... D , DOI : 10.1007 / 978-3-642-15775-2 , ISBN 978-3-642-15774-5
- ^ Шульц, Андре (2011), «Рисование 3-многогранников с хорошим разрешением вершин» (PDF) , Журнал алгоритмов и приложений графов , 15 (1): 33–52, doi : 10.7155 / jgaa.00216
- ^ Демейн, Эрик Д .; Шульц, Андре (2017), "Вложение сложены многогранники на сетке полиномиального размера", дискретная и вычислительная геометрия , 57 (4): 782-809, Arxiv : 1403,7980 , DOI : 10.1007 / s00454-017-9887-6 , MR 3639604
- ^ Айхольцер, Освин; Ченг, Ховард; Devadoss, Satyan L .; Хакл, Томас; Хубер, Стефан; Ли, Брайан; Ристески, Андрей (2012), "Что делает дерево прямым скелетом?" (PDF) , Материалы 24-й Канадской конференции по вычислительной геометрии (CCCG'12)
- ^ Барнетт, Дэвид В .; Грюнбаум, Бранко (1970), "Preassigning формы лица" , Тихоокеанский журнал математика , 32 (2): 299-306, DOI : 10,2140 / pjm.1970.32.299 , МР 0259744
- ^ Барнетт, David W. (1970), "Проекции 3-многогранников", Израиль Журнал математики , 8 (3): 304-308, DOI : 10.1007 / BF02771563 , S2CID 120791830
- ^ Харт, Джордж У. (1997), «Вычисление канонических многогранников» , « Математика в образовании и исследованиях» , 6 (3): 5–10.
- ^ Берн, Маршалл; Эпштейн, Дэвид (2001), "Оптимальные преобразования Мёбиуса для визуализации информации и создания сеток", Proc. 7-й Worksh. Алгоритмы и структуры данных (WADS 2001) , лекция. Примечания Комп. Sci., 2125 , Springer, стр. 14–25, arXiv : cs / 0101006 , doi : 10.1007 / 3-540-44634-6_3 , S2CID 3266233
- ^ Шрамм, Одед (1992), «Как поместить яйцо в клетку», Inventiones Mathematicae , 107 (3): 543–560, Bibcode : 1992InMat.107..543S , doi : 10.1007 / BF01231901 , MR 1150601 , S2CID 189830473
- ^ Ривин, Игорь (1996), "Характеристика идеального многогранников в гиперболической 3-пространстве", Анналы математики , второй серии 143 (1): 51-70, DOI : 10,2307 / 2118652 , JSTOR 2118652 , МР 1370757
- ^ Дилленкур, Майкл Б.; Смит, Уоррен Д. (1996), "Граф-теоретические условия для inscribability и Делон реализуемости" , дискретная математика , 161 (1-3): 63-77, DOI : 10.1016 / 0012-365X (95) 00276-3 , М.Р. 1420521
- ^ Рихтер-Геберт, Юрген (1996), Пространства реализации многогранников , Лекционные заметки по математике, 1643 , Springer-Verlag, ISBN 978-3-540-62084-6
- ^ а б Эпштейн, Дэвид (2020), «Деревья и их графики», Дискретная и вычислительная геометрия , 64 (2): 259–289, arXiv : 1510.03152 , doi : 10.1007 / s00454-020-00177-0 , MR 4131546
- ^ Хонг, Сок-Хи; Нагамочи, Хироши (2011), «Расширение теоремы Стейница на восходящие звездообразные многогранники и сферические многогранники», Algorithmica , 61 (4): 1022–1076, DOI : 10.1007 / s00453-011-9570-x , MR 2852056 , S2CID 12622357
- ^ Эпштейн, Дэвид ; Мамфорд, Елена (2014), "Теоремы Стейница для простых ортогональных многогранников", Журнал вычислительной геометрии , 5 (1): 179–244, MR 3259910
- ^ Слепой, Росвита; Мани-Levitska, Питер (1987), "головоломки и многогранник изоморфизмы", Aequationes Mathematicae , 34 (2-3): 287-297, DOI : 10.1007 / BF01830678 , МР 0921106 , S2CID 120222616
- ^ Kalai, Gil (1988), "Простой способ отличить простой многогранник от его графа", Journal of Combinatorial Theory , Series A, 49 (2): 381–383, doi : 10.1016 / 0097-3165 (88) 90064- 7 , Руководство по ремонту 0964396
- ^ Зиглер, Гюнтер М. (2008), «Многогранные поверхности высокого рода», Дискретная дифференциальная геометрия , Обервольфахские семинары, 38 , Springer, стр. 191–213, arXiv : math / 0412093 , doi : 10.1007 / 978-3-7643- 8621-4_10 , ISBN 978-3-7643-8620-7, Руководство по ремонту 2405667 , S2CID 15911143
- ^ Ловаса, Ласло (2001), "Steinitz представление многогранников и число Колен де Вердьер", Журнал комбинаторной теории , Series B, 82 (2): 223-236, DOI : 10,1006 / jctb.2000.2027 , МР 1842113