Аполлоническая сеть - Apollonian network
В комбинаторная математика, Аполлоническая сеть является неориентированный граф образованный процессом рекурсивного деления треугольника на три меньших треугольника. Аполлонические сети можно эквивалентно определить как планарный 3-деревья, максимальные плоские хордовые графы, уникально 4-цветный планарные графы, а графики сложенные многогранники. Они названы в честь Аполлоний Пергский, который изучал родственную конструкцию упаковки кругов.
Определение
Аполлоническая сеть может быть образована, исходя из единственного треугольника. встроенный в Евклидова плоскость, путем многократного выбора треугольной грани вложения, добавления новой вершины внутри грани и соединения новой вершины с каждой вершиной грани, содержащей ее. Таким образом, треугольник, содержащий новую вершину, разбивается на три меньших треугольника, которые, в свою очередь, могут быть разделены таким же образом.
Примеры
В полные графики на трех и четырех вершинах, K3 и K4, являются аполлоническими сетями. K3 формируется, начиная с треугольника и не выполняя никаких подразделений, а K4 формируется путем выполнения единственного подразделения перед остановкой.
В График Гольднера – Харари это аполлоническая сеть, которая образует наименьшую негамильтониан максимальный планарный граф.[1] Еще одну более сложную аполлоническую сеть использовали Нишизеки (1980) чтобы привести пример 1-жесткий негамильтонов максимальный планарный граф.
Теоретико-графические характеристики
Помимо определения рекурсивным подразделением треугольников, аполлонические сети имеют несколько других эквивалентных математических характеристик. Они хордовый максимальные планарные графы, хордовые многогранные графы, а планарный 3-деревья. Они уникально 4-цветный планарные графы и плоские графы с уникальным Шнайдер Вуд разложение на три дерева. Это максимальные плоские графы с шириной три, класс графов, которые можно охарактеризовать запрещенные несовершеннолетние или по их сводимости при Y-Δ преобразует. Это максимальные плоские графы с вырождение три. Они также являются планарными графами с заданным числом вершин, которые имеют наибольшее возможное количество треугольников, наибольшее возможное число тетраэдрических подграфов, наибольшее возможное число клик и наибольшее возможное число частей после разложения путем разделения треугольников.
Хордальность
Аполлонические сети являются примерами максимальный планарные графы, графы, к которым нельзя добавить дополнительные ребра без нарушения планарности, или, что то же самое, графы, которые можно нарисовать на плоскости так, чтобы каждая грань (включая внешнюю грань) была треугольником. Они также хордовые графы, графы, в которых каждый цикл из четырех или более вершин имеет диагональное ребро, соединяющее две непоследовательные вершины цикла, а порядок, в котором вершины добавляются в процессе подразделения, который формирует аполлоновскую сеть, является порядком исключения как хордовый граф. Это формирует альтернативную характеристику аполлоновских сетей: это в точности хордовые максимальные планарные графы или, что то же самое, хордальные многогранные графы.[2]
В аполлонической сети каждый максимальная клика представляет собой полный граф с четырьмя вершинами, образованный выбором любой вершины и трех ее предыдущих соседей. Каждый минимальный разделитель кликов (клика, которая разбивает граф на два несвязных подграфа) - это один из разделенных треугольников. Хордовый граф, в котором все максимальные клики и все минимальные разделители клик имеют одинаковый размер, называется k-дерево, и аполлонические сети являются примерами 3-деревьев. Не каждое 3-дерево является плоским, но плоские 3-деревья - это в точности аполлонические сети.
Уникальная красочность
Каждая аполлоническая сеть также является однозначно 4-раскрашиваемый граф. Поскольку это планарный граф, теорема четырех цветов подразумевает, что он имеет раскраска графика только с четырьмя цветами, но как только выбраны три цвета исходного треугольника, есть только один возможный выбор для цвета каждой последующей вершины, так что до перестановки набора цветов он имеет ровно одну 4-раскраску. Сложнее доказать, но это также верно, что каждый однозначно 4-раскрашиваемый плоский граф является аполлонической сетью. Следовательно, аполлонические сети также можно охарактеризовать как однозначно раскрашиваемые плоские графы.[3] Аполлоновские сети также предоставляют примеры планарных графов, в которых k- раскраски по возможности для k > 4.[4]
Аполлоновские сети - это также в точности максимальные плоские графы, которые (после фиксации внешней грани) имеют единственный Шнайдер Вуд, разбиение ребер графа на три чередующихся дерева с корнями в трех вершинах внешней грани.[5]
Ширина дерева
Аполлоновские сети не образуют семейство графов, замкнутое относительно операции взятия граф миноры, поскольку удаление ребер, но не вершин, из аполлонической сети дает граф, который не является аполлонической сетью. Однако планарный частичные 3-деревья, подграфы аполлонических сетей, мино-замкнутые. Следовательно, согласно Теорема Робертсона – Сеймура, их можно охарактеризовать конечным числом запрещенные несовершеннолетние. Минимальные запрещенные миноры для плоских частичных 3-деревьев - это четыре минимальных графа среди запрещенных миноров для планарных графов и частичных 3-деревьев: полный график K5, то полный двудольный граф K3,3, график октаэдр, а график пятиугольная призма. Аполлоновские графы - это максимальные графы, в которых ни один из этих четырех графов не является второстепенным.[6]
А Y-Δ преобразование, операция, которая заменяет вершину третьей степени в графе треугольником, соединяющим ее соседей, достаточна (вместе с удалением параллельных ребер), чтобы свести любую аполлоновскую сеть к одному треугольнику и, в более общем смысле, к планарным графам, которые могут быть сведенные к одному ребру преобразованиями Y-Δ, удаление параллельных ребер, удаление вершин первой степени и сжатие вершин второй степени - это в точности плоские частичные 3-деревья. Двойственные графы планарных частичных 3-деревьев образуют другое семейство минорно-замкнутых графов и представляют собой в точности плоские графы, которые могут быть сведены к единственному ребру с помощью преобразований Δ-Y, удаления параллельных ребер, удаления вершин первой степени и сжатие вершин второй степени.[7]
Вырождение
В каждом подграфе аполлонической сети последняя добавленная вершина имеет степень не более трех, поэтому аполлонические сети имеют вырождение три. Таким образом, порядок, в котором вершины добавляются для создания сети, является порядком вырождения, а аполлоновские сети совпадают с 3-вырожденными максимальными планарными графами.
Крайность
Другая характеристика аполлонических сетей включает их возможность подключения. Любой максимальный планарный граф можно разложить на максимальные планарные подграфы с 4 вершинами, разделив его по разделяющим его треугольникам (треугольникам, которые не являются гранями графа): для любого нефлицевого треугольника: можно сформировать два меньших максимальных плоских графа, один состоит из части внутри треугольника, а другой - из части вне треугольника. Максимальные плоские графы без разделяющих треугольников, которые могут быть образованы повторными разбиениями этого типа, иногда называют блоками, хотя это имя также использовалось для двусвязные компоненты графа, который сам не двусвязен. Аполлоническая сеть - это максимальный планарный граф, в котором все блоки изоморфный к полному графикуK4.
В экстремальная теория графов, Аполлонические сети также являются п-вершинные плоские графы, в которых количество блоков максимально, п − 3, и планарные графы, в которых число треугольников достигает максимума, 3п − 8. Поскольку каждый K4 подграф планарного графа должен быть блоком, это также планарные графы, в которых количество K4 подграфов достигает максимума, п − 3, и графики, в которых количество клики любого типа достигает максимума, 8п − 16.[8]
Геометрические реализации
Строительство из круглых насадок
Аполлонические сети названы в честь Аполлоний Пергский, которые изучили Проблема Аполлония построения окружности, касательной к трем другим окружностям. Один из методов построения аполлонических сетей состоит в том, чтобы начать с трех касательных друг к другу кругов, а затем многократно вписать еще один круг в промежуток, образованный тремя ранее нарисованными кругами. Полученный таким образом фрактальный набор кругов называется Аполлонийская прокладка.
Если процесс создания аполлонической прокладки прекращается раньше, имея только конечный набор окружностей, то граф, имеющий одну вершину для каждой окружности и одно ребро для каждой пары касательных окружностей, является аполлонической сетью.[9] Существование набора касательных окружностей, касания которых представляют данную аполлоновскую сеть, образует простой пример Теорема Кебе – Андреева – Терстона об упаковке кругов, который утверждает, что любой планарный граф может быть таким же образом представлен касательными окружностями.[10]
Многогранники
Аполлонические сети плоские 3-связные графы и, следовательно, по Теорема Стейница, всегда можно представить в виде графиков выпуклых многогранники. Выпуклый многогранник, представляющий аполлоновскую сеть, является трехмерным сложенный многогранник. Такой многогранник может быть получен из тетраэдра, многократно наклеивая дополнительные тетраэдры по одному на его треугольные грани. Следовательно, аполлонические сети также могут быть определены как графы сложенных трехмерных многогранников.[11] Можно найти представление любой аполлонической сети в виде выпуклого трехмерного многогранника, в котором все координаты являются целыми числами полиномиального размера, что лучше, чем то, что известно для других плоских графов.[12]
Сетки треугольника
Рекурсивное деление треугольников на три меньших треугольника исследовалось как сегментация изображения техника в компьютерное зрение к Элкок, Гаргантини и Уолш (1987); в этом контексте они назвали это разложение на троичный разносторонний треугольник. Они заметили, что, помещая каждую новую вершину в центроид окружающего его треугольника, триангуляцию можно выбрать таким образом, чтобы все треугольники имели равные площади, хотя не все они имели одинаковую форму. В более общем смысле, аполлонические сети могут быть нарисованы на плоскости с любой заданной областью на каждой грани; если области рациональное число, как и все координаты вершины.[13]
Также возможно выполнить процесс разделения треугольника для формирования аполлонической сети таким образом, чтобы на каждом шаге длины ребер были рациональными числами; остается открытым вопрос, есть ли у каждого плоского графа рисунок с этим свойством.[14] Это возможно в полиномиальное время найти чертеж плоского 3-дерева с целочисленными координатами, минимизирующего площадь Ограничительная рамка чертежа, и проверить, можно ли нарисовать данное плоское 3-дерево с его вершинами на заданном наборе точек.[15]
Свойства и приложения
Графики без совпадений
Пламмер (1992) использовали аполлонические сети для построения бесконечного семейства максимальных плоских графов с четным числом вершин, но без идеальное соответствие. Графики Пламмера формируются в два этапа. На первом этапе, начиная с треугольника abc, можно повторно разбить треугольную грань подразделения, содержащего ребро до н.э: результат - граф, состоящий из пути из а к последней вершине подразделения вместе с ребром от каждой вершины пути до каждой из б и c. На втором этапе каждая из треугольных граней полученного плоского графа разбивается еще раз. Если путь от а до конечного подразделения вершина первого этапа имеет четную длину, то число вершин в общем графе также четное. Однако примерно 2/3 вершин приходится на второй этап; они образуют независимый набор, и не могут быть сопоставлены друг с другом, а также нет достаточного количества вершин вне независимого набора, чтобы найти совпадения для всех из них.
Хотя сами аполлонические сети могут не иметь идеального соответствия, плоский двойной графы аполлонических сетей 3-регулярные графы без обрезать края, поэтому по теореме Петерсен (1891) у них гарантировано будет хотя бы одно идеальное совпадение. Однако в этом случае известно больше: двойники аполлоновских сетей всегда имеют экспоненциальное количество совершенных сопоставлений.[16] Ласло Ловас и Майкл Д. Пламмер предположил, что аналогичная экспоненциальная нижняя граница верна в более общем случае для любого 3-регулярного графа без разрезных ребер, результат, который позже был доказан.
Графики степенного закона
Андраде и др. (2005) учился законы власти в последовательности степеней частного случая сетей этого типа, образованного разделением всех треугольников одинаковое количество раз. Они использовали эти сети для моделирования упаковки пространства частицами разных размеров. Основываясь на своей работе, другие авторы ввели случайные аполлонические сети, образованные путем многократного выбора случайной грани для подразделения, и показали, что они также подчиняются степенным законам в их распределении степеней. [17] и имеют небольшие средние расстояния.[18] Алан М. Фриз и Харалампос Э. Цуракакис проанализировали высшие степени и собственные значения случайных аполлонических сетей.[19] Андраде и др. также заметил, что их сети удовлетворяют эффект маленького мира, что все вершины находятся на небольшом расстоянии друг от друга. Основываясь на численных данных, они оценили среднее расстояние между случайно выбранными парами вершин в п-вершинная сеть этого типа должна быть пропорциональна (бревно п)3/4, но позже исследователи показали, что среднее расстояние на самом деле пропорционально бревно п.[20]
Распределение углов
Батлер и Грэм (2010) заметил, что если каждая новая вершина помещается в стимулятор его треугольника, так что ребра новой вершины разделить углы пополам треугольника, то набор троек углов треугольников в подразделении, когда он интерпретируется как тройки барицентрические координаты очков в равносторонний треугольник, сходится по форме к Треугольник Серпинского по мере роста количества уровней подразделения.
Гамильтоничность
Такео (1960) ошибочно утверждал, что все аполлонические сети имеют Гамильтоновы циклы; Тем не менее График Гольднера – Харари дает контрпример. Если в аполлонической сети есть стойкость больше единицы (это означает, что при удалении любого набора вершин из графа остается меньшее количество компонент связности, чем количество удаленных вершин), то он обязательно имеет гамильтонов цикл, но существуют негамильтоновы аполлоновы сети, прочность которых равна единице. .[21]
Перечисление
В комбинаторное перечисление проблема подсчета аполлонических триангуляций изучалась Такео (1960), которые показали, что у них есть простые производящая функция ж(Икс) описывается уравнением ж(Икс) = 1 + Икс(ж(Икс))3.В этой производящей функции член степени п подсчитывает количество аполлонических сетей с фиксированным внешним треугольником и п + 3 Таким образом, количество аполлонических сетей (с фиксированным внешним треугольником) на 3, 4, 5, ... вершинах равно:
последовательность, которая также считается тройные деревья и разбиение выпуклых многоугольников на многоугольники с нечетными сторонами. Например, существует 12 аполлоновских сетей с 6 вершинами: три образованы путем однократного деления внешнего треугольника и последующего деления двух из полученных треугольников, а девять образованы путем однократного деления внешнего треугольника, разделение одного из его треугольников, а затем разделение одного из получившихся меньших треугольников.
История
Биркгоф (1930) - это ранняя статья, в которой используется двойная форма аполлонических сетей, плоские карты, сформированные путем многократного размещения новых областей в вершинах более простых карт, как класс примеров плоских карт с небольшим количеством раскрасок.
Геометрические структуры, тесно связанные с аполлоническими сетями, изучались в многогранная комбинаторика по крайней мере с начала 1960-х годов, когда они использовались Грюнбаум (1963) описывать графы, которые могут быть реализованы как граф многогранника только одним способом, без размерных или комбинаторных неоднозначностей, и Луна и Мозер (1963) найти симплициальные многогранники без длинных путей. В теория графов, тесная связь между планарностью и шириной дерева восходит к Робертсон и Сеймур (1984), который показал, что каждое минорно-замкнутое семейство графов либо имеет ограниченную ширину дерева, либо содержит все плоские графы. Плоские 3-деревья, как класс графов, явно рассматривались Хакими и Шмейхель (1979), Алон и Каро (1984), Патил (1986), и многие авторы после них.
Название «Аполлоническая сеть» было дано Андраде и др. (2005) к изучаемым ими сетям, в которых уровень разделения треугольников одинаков во всей сети; эти сети геометрически соответствуют типу сложенного многогранника, называемого Kleetope.[22] Другие авторы применили то же самое название к планарным 3-деревьям в своей работе, обобщая модель Андраде и др. случайным аполлоническим сетям.[18] Сгенерированные таким образом триангуляции также получили название «сложенные триангуляции».[23] или «стек-триангуляции».[24]
Смотрите также
- Барицентрическое подразделение, другой метод деления треугольников на более мелкие.
- Поверхность сечения петли, еще один метод деления треугольников на более мелкие.
Примечания
- ^ Этот график назван в честь работы Гольднер и Харари (1975); однако он появляется раньше в литературе, например в Грюнбаум (1967), п. 357.
- ^ Эквивалентность планарных 3-деревьев и хордовых максимальных планарных графов была заявлена без доказательства Патил (1986). Для доказательства см. Маркензон, Юстель и Пасиорник (2006). Для более общей характеристики хордовых планарных графов и эффективного алгоритма распознавания этих графов см. Кумар и Мадхаван (1989). Наблюдение, что каждый хордовый многогранный граф является максимально плоским, было явно сформулировано Герлах (2004).
- ^ Фаулер (1998).
- ^ Тот факт, что аполлонические сети минимизируют количество раскрасок с более чем четырьмя цветами, был показан в двойной форме для раскраски карт по Биркгоф (1930).
- ^ Фельснер и Зикфельд (2008); Бернарди и Бонишон (2009).
- ^ Два запрещенных минора для плоских графов задаются формулой Теорема Вагнера. Для запрещенных миноров для частичных 3-деревьев (которые включают также непланарные График Вагнера ) видеть Арнборг, Проскуровски и Корниэль (1986) и Бодлендер (1998). Прямые доказательства того, что октаэдрический граф и граф пятиугольной призмы являются единственными двумя планарными запрещенными минорами, см. Дай и Сато (1990) и Эль-Маллах и Колборн (1990).
- ^ Политоф (1983) ввел Δ-Y-приводимые планарные графы и охарактеризовал их в терминах запрещенных гомеоморфных подграфов. Двойственность между приводимыми графами Δ-Y и Y-Δ, запрещенные второстепенные характеристики обоих классов и связь с планарными частичными 3-деревьями - все из Эль-Маллах и Колборн (1990).
- ^ Для характеристики в терминах максимального числа треугольников в плоском графе см. Хакими и Шмейхель (1979). Алон и Каро (1984) процитируйте этот результат и дайте характеристики в терминах классов изоморфизма блоков и количества блоков. Оценка общего числа клик легко следует из оценок треугольников и K4 подграфы, а также явно указывается Дерево (2007), который приводит аполлоническую сеть в качестве примера, показывающего, что эта граница жесткая. Обобщения этих оценок на неплоские поверхности см. Дуймович и др. (2009).
- ^ Андраде и др. (2005).
- ^ Терстон (1978–1981).
- ^ См., Например, Внизу, Де Лоэра и Рихтер-Геберт (2000).
- ^ Демейн и Шульц (2011).
- ^ Бидл и Руис Веласкес (2010).
- ^ Чтобы разделить треугольник с рациональными длинами сторон, чтобы меньшие треугольники также имели рациональные длины сторон, см. Альмеринг (1963). О прогрессе в решении общей проблемы поиска плоских чертежей с рациональной длиной кромок см. Гилен, Го и Маккиннон (2008).
- ^ Для чертежей с целыми координатами см. Mondal et al. (2010), а рисунки на данном наборе вершин см. Нишат, Мондаль и Рахман (2011).
- ^ Хименес и Киви (2010).
- ^ Цуракакис (2011)
- ^ а б Чжоу и др. (2004); Чжоу, Ян и Ван (2005).
- ^ Frieze & Tsourakakis (2011)
- ^ Альбенк и Маркерт (2008);Zhang et al. (2008).
- ^ Видеть Нишизеки (1980) для 1-жесткого негамильтонова примера, Бёме, Гарант и Ткач (1999) для доказательства гамильтоновости аполлоновских сетей с большей жесткостью и Герлах (2004) для распространения этого результата на более широкий класс планарных графов.
- ^ Грюнбаум (1963); Грюнбаум (1967).
- ^ Алон и Каро (1984); Зикфельд и Зиглер (2006); Badent et al. (2007); Фельснер и Зикфельд (2008).
- ^ Альбенке и Маркерт (2008); Бернарди и Бонишон (2009); Хименес и Киви (2010).
Рекомендации
- Альбенке, Мари; Маркерт, Жан-Франсуа (2008), «Некоторые семейства увеличивающихся планарных карт», Электронный журнал вероятностей, 13: 1624–1671, arXiv:0712.0593, Дои:10.1214 / ejp.v13-563, МИСТЕР 2438817, S2CID 2420262
- Альмеринг, Дж. Х. Дж. (1963), «Рациональные четырехугольники», Indagationes Mathematicae, 25: 192–199, Дои:10.1016 / S1385-7258 (63) 50020-1, МИСТЕР 0147447.
- Алон, Н.; Каро, Y. (1984), «О числе подграфов заданного типа плоских графов с заданным числом вершин», в Rosenfeld, M .; Zaks, J. (ред.), Выпуклость и теория графов: материалы конференции по теории выпуклости и графов, Израиль, март 1981 г., Annals of Discrete Mathematics 20, North-Holland Mathematical Studies 87, Elsevier, стр. 25–36, ISBN 978-0-444-86571-7, МИСТЕР 0791009.
- Андраде, Хосе С., младший; Herrmann, Hans J .; Андраде, Роберто Ф. С .; да Силва, Лучано Р. (2005), "Аполлонические сети: одновременно безмасштабный, малый мир, евклидово, заполнение пространства и совпадающие графы", Письма с физическими проверками, 94 (1): 018702, arXiv:cond-mat / 0406295, Bibcode:2005PhRvL..94a8702A, Дои:10.1103 / Physrevlett.94.018702, PMID 15698147.
- Arnborg, S .; Проскуровский, А .; Корниэль, Д. (1986), Запрещенные второстепенные характеристики частичных 3-деревьев, Технический отчет CIS-TR-86-07, Департамент компьютерных и информационных наук, Орегонский университет. Как цитирует Эль-Маллах и Колборн (1990).
- Бадент, Мелани; Бинуччи, Карла; Ди Джакомо, Эмилио; Дидимо, Уолтер; Фельснер, Стефан; Джордано, Франческо; Кратохвил, Ян; Палладино, Пьетро; Патриньяни, Маурицио; Тротта, Франческо (2007), "Гомотетические треугольные контактные представления плоских графов", Канадская конференция по вычислительной геометрии (PDF).
- Внизу, Александр; Де Лоэра, Хесус А.; Рихтер-Геберт, Юрген (2000), Сложность нахождения малых триангуляций выпуклых 3-многогранников, arXiv:математика / 0012177, Bibcode:2000математика ..... 12177B.
- Бернарди, Оливье; Бонишон, Николас (2009), "Интервалы в каталонских решетках и реализаторы триангуляций", Журнал комбинаторной теории, Серия А, 116 (1): 55–75, Дои:10.1016 / j.jcta.2008.05.005, МИСТЕР 2469248.
- Бидль, Тереза; Руис Веласкес, Лесвия Елена (2010), «Рисование трех плоских деревьев с заданными областями лица», Графический рисунок, 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Исправленные статьи, Конспект лекций по информатике, 5849, Springer-Verlag, стр. 316–322, Дои:10.1007/978-3-642-11805-0_30.
- Биркофф, Джордж Д. (1930), «О количестве способов раскраски карты», Труды Эдинбургского математического общества, (2), 2 (2): 83–91, Дои:10.1017 / S0013091500007598.
- Бодландер, Ханс Л. (1998), "Частичный k-арборетум графов с ограниченной шириной дерева », Теоретическая информатика, 209 (1–2): 1–45, Дои:10.1016 / S0304-3975 (97) 00228-4, HDL:1874/18312, МИСТЕР 1647486.
- Бёме, Томас; Harant, Jochen; Ткач, Михал (1999), "Гамильтоновы более одного жесткого хордового плоского графа", Журнал теории графов, 32 (4): 405–410, Дои:10.1002 / (SICI) 1097-0118 (199912) 32: 4 <405 :: AID-JGT8> 3.3.CO; 2-Q, МИСТЕР 1722793.
- Батлер, С .; Грэм, Рон (2010), «Повторяющиеся треугольные разбиения», в Katona, G .; Шрайвер, А.; Szonyi, T. (ред.), Праздник комбинаторики и информатики (PDF), Математические исследования Общества Бойяи, 29, Heidelberg: Springer-Verlag, стр. 23–42..
- Дай, Уэйн Вэй-Мин; Сато, Масао (1990), "Минимальная запрещенная второстепенная характеристика плоских частичных 3-деревьев и применение к компоновке схемы", Международный симпозиум IEEE по схемам и системам, 4, стр. 2677–2681, Дои:10.1109 / ISCAS.1990.112560, S2CID 122926229
- Демейн, Эрик; Шульц, Андре (2011), "Вложение многогранников с накоплением в сетку полиномиального размера", Proc. Симпозиум ACM-SIAM по дискретным алгоритмам (PDF), pp. 1177–1187, архивировано с оригинал (PDF) на 2011-06-01, получено 2011-03-07.
- Дуймович, Вида; Фиявж, Гашпер; Джорет, Гвенаэль; Вуд, Дэвид Р. (2009), «Максимальное количество клик в графе, вложенном в поверхность», Европейский журнал комбинаторики, 32 (8): 1244–1252, arXiv:0906.4142, Bibcode:2009arXiv0906.4142D, Дои:10.1016 / j.ejc.2011.04.001, S2CID 1733300.
- El-Mallah, Ehab S .; Колборн, Чарльз Дж. (1990), «О двух двойственных классах планарных графов», Дискретная математика, 80 (1): 21–40, Дои:10.1016 / 0012-365X (90) 90293-Q, МИСТЕР 1045921.
- Elcock, E.W .; Гаргантини, I .; Уолш, Т. Р. (1987), "Треугольное разложение", Вычисления изображений и зрения, 5 (3): 225–231, Дои:10.1016/0262-8856(87)90053-9.
- Фельснер, Стефан; Зикфельд, Флориан (2008), «О количестве планарных ориентаций с заданными степенями» (PDF), Электронный журнал комбинаторики, 15 (1): R77, arXiv:математика / 0701771, Bibcode:2007 математика ...... 1771F, Дои:10.37236/801, МИСТЕР 2411454, S2CID 13893657.
- Frieze, Алан М.; Цуракакис, Харалампос Э. (2011), Вершины высоких степеней, собственные значения и диаметр случайных аполлоновских сетей, arXiv:1104.5259, Bibcode:2011arXiv1104.5259F.
- Фаулер, Томас (1998), Уникальная раскраска плоских графов (PDF), Кандидат наук. диссертация, математический факультет Технологического института Джорджии.
- Гилен, Джим; Го, Анжи; Маккиннон, Дэвид (2008), "Прямые вложения кубических плоских графов с целыми длинами ребер", Журнал теории графов, 58 (3): 270–274, Дои:10.1002 / jgt.20304, МИСТЕР 2419522.
- Герлах, Т. (2004), "Прочность и гамильтоничность одного класса плоских графов", Дискретная математика, 286 (1–2): 61–65, Дои:10.1016 / j.disc.2003.11.046, МИСТЕР 2084280.
- Goldner, A .; Харари, Ф. (1975), "Замечание о наименьшем негамильтоновом максимальном плоском графе", Бык. Malaysian Math. Soc., 6 (1): 41–42. См. Также тот же журнал 6(2): 33 (1975) и 8: 104-106 (1977). Ссылка из список публикаций Харари.
- Грюнбаум, Бранко (1963), "Однозначные многогранные графы", Израильский математический журнал, 1 (4): 235–238, Дои:10.1007 / BF02759726, МИСТЕР 0185506, S2CID 121075042.
- Грюнбаум, Бранко (1967), Выпуклые многогранники, Wiley Interscience.
- Хакими, С.Л.; Шмейхель, Э. Ф. (1979), "О количестве циклов длины k в максимальном плоском графе », Журнал теории графов, 3 (1): 69–86, Дои:10.1002 / jgt.3190030108, МИСТЕР 0519175.
- Хименес, Андреа; Киви, Маркос (2010), Подсчет совершенных паросочетаний кубических графов в геометрическом дуальном, arXiv:1010.5918, Bibcode:2010arXiv1010.5918J.
- Кумар, П. Шриниваса; Мадхаван, К. Э. Вени (1989), "Новый класс разделителей и планарность хордовых графов", Основы программных технологий и теоретической информатики, Девятая конференция, Бангалор, Индия, 19–21 декабря 1989 г., Труды, Конспект лекций по информатике, 405, Springer-Verlag, стр. 30–43, Дои:10.1007/3-540-52048-1_30, МИСТЕР 1048636.
- Маркензон, Л .; Justel, C.M .; Пасиорник, Н. (2006), "Подклассы k-деревья: Характеристика и признание », Дискретная прикладная математика, 154 (5): 818–825, Дои:10.1016 / j.dam.2005.05.021, МИСТЕР 2207565.
- Мондаль, Дебаджьоти; Нишат, Рахнума Ислам; Рахман, штат Мэриленд Сайдур; Алам, Мухаммад Джавахерул (2010), "Чертежи плоских 3-х деревьев с минимальной площадью", Канадская конференция по вычислительной геометрии (PDF).
- Moon, J. W .; Мозер, Л. (1963), «Простые пути на многогранниках», Тихоокеанский математический журнал, 13 (2): 629–631, Дои:10.2140 / pjm.1963.13.629, МИСТЕР 0154276.
- Нишат, Рахнума Ислам; Мондаль, Дебаджьоти; Рахман, Мэри Саидур (2011), "Вложения множества точек плоских 3-деревьев", Графический рисунок, 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., отредактированные избранные статьи, Конспект лекций по информатике, 6502, Springer-Verlag, стр. 317–328, Дои:10.1007/978-3-642-18469-7_29.
- Нисизэки, Такао (1980), "1-жесткий негамильтонов максимальный планарный граф", Дискретная математика, 30 (3): 305–307, Дои:10.1016 / 0012-365X (80) 90240-X, МИСТЕР 0573648.
- Патил, Х. П. (1986), "О структуре k-деревья ", Журнал комбинаторики, информации и системных наук, 11 (2–4): 57–64, МИСТЕР 0966069.
- Петерсен, Юлиус (1891), «Теория регулятивных графов», Acta Mathematica, 15: 193–220, Дои:10.1007 / BF02392606.
- Пламмер, Майкл Д. (1992), "Расширение паросочетаний в плоских графах IV", Дискретная математика, 109 (1–3): 207–219, Дои:10.1016 / 0012-365X (92) 90292-N, МИСТЕР 1192384.
- Политоф, Т. (1983), Определение характеристик и эффективное вычисление надежности приводимых сетей Δ-Y, Кандидат наук. дипломная работа, Калифорнийский университет, Беркли. Как цитирует Эль-Маллах и Колборн (1990).
- Робертсон, Нил; Сеймур, П. Д. (1984), "Миноры графа. III. Плоская ширина дерева", Журнал комбинаторной теории, Серия B, 36 (1): 49–64, Дои:10.1016/0095-8956(84)90013-3, МИСТЕР 0742386.
- Такео, Фудзио (1960), "О триангулированных графах. I", Бык. Fukuoka Gakugei Univ. III, 10: 9–21, МИСТЕР 0131372. На ошибку в отношении гамильтоновости указал MathSciNet рецензент В. Т. Тутте.
- Терстон, Уильям (1978–1981), Геометрия и топология трехмерных многообразий, Конспект лекций Принстона.
- Цуракакис, Харалампос Э. (2011), Последовательность степеней случайных аполлонических сетей.
- Вуд, Дэвид Р. (2007), «О максимальном количестве клик в графе», Графы и комбинаторика, 23 (3): 337–352, arXiv:математика / 0602191, Дои:10.1007 / s00373-007-0738-8, МИСТЕР 2320588, S2CID 46700417.
- Чжан, Чжунчжи; Чен, Личао; Чжоу, Shuigeng; Фанг, Луджун; Гуань, Цзихун; Цзоу, Тао (2008), "Аналитическое решение средней длины пути для аполлонических сетей", Физический обзор E, 77 (1): 017102, arXiv:0706.3491, Bibcode:2008PhRvE..77a7102Z, Дои:10.1103 / PhysRevE.77.017102, PMID 18351964, S2CID 30404208.
- Чжоу, Дао; Ян, банда; Ван, Бинг-Хонг (2005), "Максимальные плоские сети с большим коэффициентом кластеризации и степенным распределением степеней", Физический обзор E, 71 (4): 046141, arXiv:cond-mat / 0412448, Bibcode:2005PhRvE..71d6141Z, Дои:10.1103 / PhysRevE.71.046141, PMID 15903760, S2CID 21740312.
- Чжоу, Дао; Ян, банда; Чжоу, Пей-Лин; Фу, Чжун-Цянь; Ван, Бинг-Хун (2004), Случайные аполлонические сети, arXiv:cond-mat / 0409414v2, Bibcode:2004 втор.мат..9414Z.
- Зикфельд, Флориан; Циглер, Гюнтер М. (2006), «Целочисленные реализации многогранников с накоплением», Практикум по геометрической и топологической комбинаторике (PDF).