Граф Аполлонія

Граф Аполлонія — неорієнтований граф, утворений рекурсивним процесом поділу трикутника на три менші трикутники. Графи Аполлонія можна еквівалентно визначити як планарні 3-дерева, як максимальні планарні хордальні графи, як однозначно 4-фарбовані планарні графи або як графи блокових многогранників. Графи названо ім'ям Аполлонія Перзького, який вивчав пов'язані побудови пакування кіл.

Граф Аполлонія

Граф Голднера — Харарі, негамільтонів граф Аполлонія

Визначення

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

Приклади

Повні графи з трьома та чотирма вершинами, K₃ та K₄ є графами Аполлонія. K₃ утворюється з початкового трикутника без подальших операцій поділу граней, тоді як K₄ утворюється однією операцією поділу.

Граф Голднера — Харарі є графом Аполлонія, а також найменшим максимальним негамільтоновим планарним графом^[1]. Інший, складніший граф Аполлонія, використав Нішизекі^[2] як приклад 1-жорсткого негамільтонового максимального планарного графа.

Теоретичні властивості

Оскільки графи Аполлонія визначаються рекурсивним поділом трикутників, вони мають інші математичні описи. Графи є хордальними максимальними планарними графами, хордальними многогранними графами та планарними 3-деревами. Графи є однозначно 4-розфарбовуваними планарними графами та планарними графами з унікальною декомпозицією в ліс Шнайдера, що складається з трьох дерев. Графи є максимальними планарними графами з деревною шириною 3, класом графів, які можна описати їхніми забороненими графами або зведенням шляхом Y-Δ-перетворень. Графи є максимальними планарними графами із виродженістю 3. Графи є також планарними графами з даним числом вершин, які мають найбільшу можливу кількість трикутників, найбільшу можливу кількість тетраедричних підграфів, найбільшу можливу кількість клік і найбільшу можливу кількість частин після розкладання на окремі трикутники.

Хордальність

Графи Аполлонія є прикладами максимальних планарних графів, у які не можна додати ребро без порушення планарності, або, еквівалентно, графами, які можна намалювати на площині так, що будь-яка грань (зокрема й зовнішня) є трикутником. Графи є також хордальними графами, в яких кожен цикл із чотирьох або більше вершин має діагональне ребро, що з'єднує дві вершини циклу, які не є послідовними в циклі, а порядок, у якому вершини додаються в процесі побудови графа Аполлонія, є порядком виключення в хордальному графі. Ця властивість дає альтернативний опис графів Аполлонія — це точно хордальні максимальні планарні графи або, еквівалентно, хордальні многогранні графи^[3].

У графі Аполлонія будь-яка максимальна кліка — це повний граф із чотирма вершинами, утворений вибором будь-якої вершини та трьох найближчих сусідів. Будь-який мінімальний кліковий сепаратор (кліка, видалення якої розбиває граф на два незв'язні графи) — це один із розділених трикутників. Хордальний граф, у якому всі максимальні кліки і всі мінімальні клікові сепаратори мають однаковий розмір, є k-деревом, а графи Аполлонія є прикладами 3-дерев. Не всі 3-дерева планарні, але планарні 3-дерева — це точно графи Аполлонія.

Єдиність розфарбування

Будь-який граф Аполлонія має єдине 4-колірне розфарбування. Оскільки граф планарний, з теореми про чотири фарби випливає, що граф має розфарбування чотирма кольорами, але, оскільки кольори початкового трикутника фіксовані, є єдина можливість вибору кольору для нової вершини, тому з точністю до перестановки кольорів розфарбування графа буде єдиним. Складніше показати, але це також істинне, що будь-який планарний граф із єдиним розфарбуванням є графом Аполлонія. Таким чином, граф Аполлонія можна охарактеризувати як планарний граф з єдиним 4-колірним розфарбуванням^[4]. Графи Аполлонія дають приклади планарних графів, що мають найменше число k-розфарбувань для k > 4^[5].

Також графи Аполлонія — це точно максимальні планарні графи, які (якщо фіксувати зовнішню грань) мають єдиний ліс Шнайдера, розбиття ребер графа на три дерева з коренями у вершинах зовнішньої грані^[6][7].

Деревна ширина

Графи Аполлонія не утворюють сімейства графів, замкненого щодо операції взяття мінорів графа, оскільки при видаленні ребер, але не вершин, отримаємо граф, який не є графом Аполлонія. Проте, сімейство планарних часткових 3-дерев, підграфів графів Аполлонія, є мінорно замкнутим сімейством. Таким чином, згідно з теоремою Робертсона — Сеймура, їх можна охарактеризувати скінченним числом заборонених мінорів. Мінімальні заборонені мінори для планарних часткових 3-дерев — це чотири мінімальні графи для планарних графів і часткових 3-дерев: повний граф K₅, повний двочастковий граф K_3,3, граф октаедра та граф п'ятикутної призми. Графи Аполлонія є максимальними графами, які не містять цих чотирьох графів як мінорів^[8].

Перетворення Y-Δ замінює вершину степеня 3 на трикутник, що з'єднує сусідів, достатньо (разом з операцією видалення кратних ребер) для зведення графа Аполлонія до єдиного трикутника. Планарні графи, які можна звести до єдиного ребра за допомогою перетворення Y-Δ, видалення кратних ребер, видалення вершин степеня 1 і заміною вершини степеня 2 разом з ребрами на одне ребро, це точно планарні часткові 3-дерева. Двоїсті графи планарних часткових 3-дерев утворюють інше замкнуте щодо взяття мінорів сімейство графів, яке є точно тими графами, які можна звести до єдиного ребра за допомогою перетворення Δ-Y, видалення кратних ребер, видалення вершин степеня 1 і звільнення від вершин степеня 2^[9].

Виродженість

У будь-якому підграфі графа Аполлонія остання додана вершина має степінь 3, тому графи Аполлонія мають виродженість 3. Таким чином, порядок, у якому вершини додаються при створенні графа, є порядком виродження, і графи Аполлонія збігаються з 3-виродженими максимальними планарними графами.

Екстремальність

Інша властивість, що характеризує графи Аполлонія, стосується зв'язності. Будь-який максимальний планарний граф можна розкласти на 4-вершинно-зв'язні максимальні планарні підграфи поділом уздовж трикутників (які не є гранями графа) — якщо є трикутник, що не є гранню, можна утворити два менших максимальних планарних графи: один з частини, що міститься в трикутнику, інший — із зовнішньої відносно нього частини. Максимальні планарні графи без розділювальних трикутників, утворені багаторазовим розбиттям такого роду, іноді називають блоками, хоча так називають і компоненти двозв'язності графа, який сам по собі двозв'язним не є. Граф Аполлонія — це максимальний планарний граф, у якому всі блоки ізоморфні повному графу K₄.

В екстремальній теорії графів графи Аполлонія — це точно планарні графи з n вершинами, в яких число блоків досягає максимального значення n − 3, та планарні графи, в яких число трикутників максимальне і дорівнює 3n − 8. Оскільки кожен підграф K₄ планарного графа має бути блоком, на цих графах досягається максимум числа підграфів K₄ (це число дорівнює n − 3). На цих же графах досягається найбільша кількість клік будь-якого типу (число клік дорівнює 8n − 16)^[10].

Геометричні реалізації

Побудова з упакованих кіл

Приклад сітки Аполлонія

Побудова графа Аполлонія з упакованих кіл

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

Якщо процес побудови сітки Аполлонія зупинити, намалювавши лише скінченне число кіл, то граф, який має вершину для кожного кола і ребро для будь-яких двох дотичних кіл і є графом Аполлонія^[11]. Існування сножини дотичних кіл, дотики яких подають граф Аполлонія, визначає теорема Кебе — Андрєєва — Терстона, яка стверджує, що будь-який планарний граф можна подати дотичними колами^[12].

Многогранники

Триакістетраедр — реалізація графа Аполлонія з 8 вершинами у вигляді многогранника

Графи Аполлонія — це планарні 3-вершинно-зв'язні графи, і тому, за теоремою Штайніца, можуть бути завжди подані як графи опуклих многогранників. Опуклий многогранник, що подає граф Аполлонія — це тривимірний блоковий многогранник. Такі многогранники можна отримати з тетраедра багаторазовим приклеюванням додаткових тетраедрів (по одному) до трикутних граней многогранника. Таким чином, графи Аполлонія можна визначити як графи блокових тривимірних многогранників^[13]. Можна знайти подання будь-якого графа Аполлонія як опуклого тривимірного многогранника, в якому всі координати є цілими числами поліноміальної величини, що краще, ніж для інших планарних графів^[14].

Трикутні сітки

Рекурсивний поділ трикутників на три менші трикутники досліджували Елкок, Гаргантіні і Волш як техніку сегментації зображення в комп'ютерному зорі^[15]. У цьому контексті вони називають такий поділ потрійним нерівностороннім розкладанням на трикутники. Вони помітили, що при додаванні кожної нової вершини в центроїд трикутника, трикутники тріангуляції матимуть однакові площі, хоча вони й різну форму. Загальніше, графи Аполлонія можна намалювати на площині з будь-якою заздалегідь заданою площею кожної грані. Якщо площі задано як раціональні числа, такими будуть і координати вершин^[16].

Можна провести процес поділу трикутників при побудові графа Аполлонія так, що на кожному кроці довжини ребер будуть раціональними числами. Невідомо, чи будь-який планарний граф можна намалювати із такими самими властивостями^[17]. За поліноміальний час можна знайти малюнок планарного 3-дерева з цілими координатами з мінімальною площею обмежувального прямокутника і перевірити, чи можна намалювати задане планарне 3-дерево з вершинами на заданій множині точок^[18].

Властивості та застосування

Графи без досконалого парування

Пламмер^[19] використав графи Аполлонія для побудови нескінченного сімейства максимальних планарних графів із парним числом вершин, що не мають досконалого парування. Графи Пламмера будуються в два етапи. На першому етапі, починаючи з трикутника abc, багато разів повторюється поділ трикутної грані, що містить ребро bc. Отриманий граф містить шлях з a до кінцевої вершини поділу та кожна вершина цього шляху з'єднана ребрами з вершинами b і c. На другому етапі кожна (трикутна) грань отриманого планарного графа ще раз розбивається. Якщо шлях з a до кінцевої вершини розбиття першого етапу має парну довжину, загальна кількість вершин графа теж парна. Однак приблизно 2/3 вершин, вставлених на другому етапі, утворюють незалежну множину і не можуть утворювати парувань між собою, а решти вершин для утворення досконалого парування недостатньо.

Хоча самі графи Аполлонія не можуть мати досконалих парувань, двоїсті графам Аполлонія графи є 3-регулярными графами без розрізальних ребер, отже за теоремою Петерсена^[20] вони обов'язково мають принаймні одне досконале парування. Для графів Аполлонія відомо навіть більше — двоїсті графам Аполлонія графи мають експоненційно велику кількість досконалих парувань^[21]. Ласло Ловас і Майкл Д. Пламмер висловили гіпотезу, що аналогічна експоненційна нижня межа має існувати для всіх 3-регулярних графів без розрізальних ребер, що й було пізніше підтверджено.

Степеневий закон графів

Ж. Андраде, Г. Геррманн, Р. Андраде і Л. де Сільва^[11] вивчали степеневі закони послідовностей степенів особливих видів графів цього виду, утворених поділом усіх трикутників однакове число разів. Вони використовували ці графи для моделювання заповнення простору частинами різного розміру. Ґрунтуючись на їхній праці, інші автори запропонували випадкові графи Аполлонія, одержувані випадковим вибором грані для поділу, і показали, що для цих графів виконується степеневий закон у розподілі степенів вершин^[22], а також показали, що ці графи мають малі відстані^[23][24]. Фріз і Тсоуракакіс аналізували найбільші степені вершин і власні значення випадкових графів Аполлонія^[25]. Ж. Андраде, Г. Геррманн, Р. Андраде і Л. де Сільва помітили також, що їхні графи задовольняють ефекту «світ тісний» (теорія шести рукостискань), тобто всі вершини розташовані близько одна від одної. Ґрунтуючись на чисельних експериментах, вони оцінили середню відстань між випадково вибраними парами вершин у графі з n вершинами як пропорційну (log n)^3/4, але подальші дослідження показали, що середня відстань насправді пропорційна log n^[26][27].

Розподіл кутів

Батлер і Ґрем^[28] помітили, що якщо кожну нову вершину поміщати в точку перетину бісектрис трикутника, то множина трійок кутів трикутників у поділі, якщо їх інтерпретувати як барицентричні координати точок у правильному трикутнику, при зростанні рівня поділу в границі утворює трикутник Серпінського.

Гамільтоновість

Такео^[29] помилково стверджував, що всі графи Аполлонія мають гамільтонові цикли, проте граф Голднера-Харарі є контрприкладом. Якщо граф Аполлонія має жорсткість, більшу від 1 (що означає, що при видаленні будь-якого числа вершин із графа в ньому залишається зв'язних компонентів менше, ніж число видалених вершин), він обов'язково гамільтонів, але існують негамільтонові графи Аполлонія, жорсткість яких дорівнює одиниці^[30].

Перелік

Комбінаторну задачу підрахунку аполлонієвих тріангуляцій вивчав Такео^[29]. Він показав, що для числа тріангуляцій існує проста твірна функція f(x) = 1 + x(f(x))³. У цій твірній функції член степеня n містить число графів Аполлонія із зовнішнім трикутником і n + 3 вершинами. Число графів Аполлонія (із зовнішнім трикутником) і 3, 4, 5, … вершинами:

1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, … (послідовність A001764 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Ця ж послідовність задає кількість трійкових дерев і кількість розбиттів опуклого многокутника на многокутники з непарним числом сторін. Наприклад, існує 12 графів Аполлонія з 6 вершинами — три утворюються розбиттям зовнішнього трикутника з подальшим розбиттям двох з отриманих трикутників і ще дев'ять утворюються розбиттям зовнішнього трикутника і розбиттям одного з отриманих трикутників із подальшим розбиттям одного з малих трикутників.

Історія

Біркгоф^[31] є рання стаття, в якій використано двоїсту форму графів Аполлонія, планарні карти, утворені багаторазовим поміщенням нових ділянок у вершинах простіших карт, як приклад класу планарних графів з малим числом кольорів.

Геометричні структури, близькі до графів Аполлонія, вивчалися в комбінаториці многогранників від початку 1960-х років, коли Ґрюнбаум^[32] використав їх для опису графів, які можна реалізувати у многогранниках у єдиний спосіб за розмірністю і з точки зору комбінаторики. Їх використали також Мун та Мозер^[33] для пошуку симпліційних многогранників без довгих шляхів. У теорії графів тісний зв'язок між планарністю і деревною шириною простежується до статті Робертсона і Сеймура 1984 року^[34], які показали, що замкнене відносно взяття мінорів сімейство графів або має обмежену деревну ширину, або містить усі планарні графи. Планарні 3-дерева, як клас графів, розглядали Хакімі і Шмайхель^[35], Алон і Каро^[36], Патіл^[37] та багато інших авторів.

Назву «граф Аполлонія» запропоновано в статті Ж. Андраде, Г. Геррманна, Р. Андраде та Л. де Сільви^[11] для графів, у яких рівень поділу трикутників однорідний. Геометрично ці графи відповідають блоковим многогранникам (многогранникам Клі)^[32][38]. Інші автори використовували термін для ширшого класу графів, планарних 3-дерев, з метою узагальнення моделі на випадкові графи Аполлонія^[23][24]. Тріангуляцію, отриману в такий спосіб, також назвали «блоковою тріангуляцією»^{[36][39][40][6][26][7][21]}.

Див. також

• Барицентричний поділ — інший метод поділу трикутника на менші трикутники
• Луупівський поділ поверхні^[en] — ще один метод поділу трикутника на менші трикутники

Примітки

1. Цей граф названо іменами авторів статті (Goldner, Harary, 1975). Однак він і раніше з'являвся в літературі, наприклад у Ґрюнбаума (Grünbaum, 1967), стор. 357.
2. Nishizeki, 1980.
3. Еквівалентність планарних 3-дерев і хордальних максимальних планарних графів припустив без доведення Патіл (Patil, 1986). Доведення див. у статиі Маркензона, Джустела і Пакіорніка (Markenzon, Justel, Paciornik, 2006). Загальніший опис хордальних планарних графів та ефективного алгоритму їх розпізнавання див. у статті Кумара й Мадгавана (Kumar, Madhavan, 1989). Що будь-який хордальний поліедричний граф є максимальним планарним, зауважив Герлах (Gerlach, 2004).
4. Fowler, 1998.
5. Факт, що графи Аполлонія мінімізують число розфарбувань із числом кольорів більшим від 4 показав Біркгоф у двоїстій формі розфарбування карт (Birkhoff, 1930).
6. Felsner, Zickfeld, 2008.
7. Bernardi, Bonichon, 2009.
8. Два заборонені мінори для планарних графів дає теорема Вагнера. Про заборонені мінори часткових 3-дерев (які включають також непланарний граф Вагнера) див. статті Арнборга, Проскуровські, Корніела (Arnborg, Proskurowski, Corniel, 1986) і Бодлаендера (Bodlaender, 1998). Пряме доведення того, що граф октаедра та п'ятикутної призми є єдиними двома планарними забороненими мінорами, див. у статтях Даї, Сато (Dai, Sato, 1990) і Ель-Маллаха, Колбоурна (El-Mallah, Colbourn, 1990).
9. Політоф (Politof, 1983) увів звідні Δ-Y планарні графи й описав їх у термінах заборонених гомеоморфних підграфів. Двоїстість між Δ-Y і Y-Δ звідними графами, опис обох класів забороненими мінорами і зв'язок із планарними частковими 3-деревами взято зі статті Ель-Маллаха і Колбоурна (El-Mallah, Colbourn, 1990).
10. Опис утермінах найбільшого числа трикутників у планарному графі дивіться статтю Хакімі та Шмейхеля (Hakimi, Schmeichel, 1979). Алон і Саро цитують цей результат і надають опис у термінах ізоморфізму класів блоків та числа блоків (Alon, Caro, 1984). Межа загального числа клік досить просто виходить з межі числа підграфів і підграфів K₄, її навів у явному вигляді Вуд (Wood, 2007), який на прикладі графів Аполлонія показав строгість межі. Узагальнення цих меж для непланарних поверхонь дивіться в статті Дуймовича, Фіявжа, Жоре і Вуда (Dujmović, Fijavž, Joret, Wood, 2009).
11. Andrade, Herrmann, Andrade, da Silva, 2005.
12. Thurston, 1978–1981.
13. Див., наприклад, статтю Бєлова, Де Лоера й Ріхтер-Геберта (Below, De Loera, Richter-Gebert, 2000)
14. Demaine, Schulz, 2011.
15. Elcock, Gargantini, Walsh, 1987.
16. Biedl, Ruiz Velázquez, 2010.
17. Для поділу трикутника з раціональними довжинами сторін так, щоб отримані трикутники теж мали раціональні сторони, див. статтю Альмеринга (Almering, 1963). Щодо загальної проблеми пошуку планарного графа з раціональними довжинами сторін див. статтю Гілена, Гуо та Маккіннона (Geelen, Guo, McKinnon, 2008).
18. Щодо малювання з цілими координатами див. статтю Мондала, Нішата, Рахмана й Алама (Mondal, Nishat, Rahman, Alam, 2010). Щодо малювання на заданій множині вершин див. статтю Нішата, Мондала й Рахмана (Nishat, Mondal, Rahman, 2011).
19. Plummer, 1992.
20. Petersen, 1891.
21. Jiménez, Kiwi, 2010.
22. Tsourakakis, 2011.
23. Zhou, Yan, Zhou, Fu, Wang, 2004.
24. Zhou, Yan, Wang, 2005.
25. Frieze, Tsourakakis, 2011.
26. Albenque, Marckert, 2008.
27. Zhang, Chen, Zhou, Fang, 2008.
28. Butler, Graham, 2010.
29. Takeo, 1960.
30. Див. статтю Нішізекі (Nishizeki, 1980) з прикладом негамільтонового графа, який має жорсткість 1 і статтю Беме, Гаранта й Ткача (Böhme, Harant, Tkáč, 1999) з доведенням, що графи Аполлонія з більшою жорсткістю є гамільтоновими. Див. статтю Герлаха (Gerlach, 2004) з узагальненням цього результату на ширший клас планарних графів.
31. Birkhoff, 1930.
32. Grünbaum, 1963.
33. Moon, Moser, 1963.
34. Robertson, Seymour, 1984.
35. Hakimi, Schmeichel, 1979.
36. Alon, Caro, 1984.
37. Patil, 1986.
38. Grünbaum, 1967.
39. Zickfeld, Ziegler, 2006.
40. Badent, Binucci, Di Giacomo, Didimo, 2007.

Література

• Marie Albenque, Jean-François Marckert. Some families of increasing planar maps // Electronic Journal of Probability. — 2008. — Т. 13. — С. 1624–1671. — arXiv:0712.0593. — DOI:10.1214/ejp.v13-563.
• Almering. Rational quadrilaterals // Indagationes Mathematicae. — 1963. — Т. 25. — С. 192–199..
• N.Alon, Y. Caro. Convexity and Graph Theory: proceedings of the Conference on Convexity and Graph Theory, Israel, March 1981 / M. Rosenfeld, J. Zaks. — Elsevier, 1984. — С. 25–36. — (Annals of Discrete Mathematics 20, North-Holland Mathematical Studies 87) — ISBN 978-0-444-86571-7.
• José S. Andrade (Jr), Hans J. Herrmann, Roberto F. S. Andrade, Luciano R. da Silva. Apollonian Networks: Simultaneously Scale-Free, Small World, Euclidean, Space Filling, and with Matching Graphs // Physical Review Letters. — 2005. — Т. 94. — С. 018702. — arXiv:cond-mat/0406295. — DOI:10.1103/physrevlett.94.018702.
• S. Arnborg, A. Proskurowski, D. Corniel. Forbidden Minors Characterization of Partial 3-trees. — Dept. of Computer and Information Science, University of Oregon, 1986. — (Technical Report CIS-TR-86-07). Как процитировано в статье Эль-Маллаха и Колбоурна (El-Mallah, Colbourn, 1990).
• Melanie Badent, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Stefan Felsner, Francesco Giordano, Jan Kratochvíl, Pietro Palladino, Maurizio Patrignani, Francesco Trotta. Canadian Conference on Computational Geometry. — 2007.
• Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes. — 2000.
• Olivier Bernardi, Nicolas Bonichon. Intervals in Catalan lattices and realizers of triangulations // Journal of Combinatorial Theory. — 2009. — Т. 116, вип. 1. — С. 55–75. — (Series A). — DOI:10.1016/j.jcta.2008.05.005.
• Therese Biedl, Lesvia Elena Ruiz Velázquez. Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22–25, 2009, Revised Papers. — Springer-Verlag, 2010. — Т. 5849. — С. 316–322. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-11805-0_30.
• George D. Birkhoff. On the number of ways of colouring a map // Proceedings of the Edinburgh Mathematical Society. — 1930. — Т. 2. — С. 83–91. — ((2)). — DOI:10.1017/S0013091500007598.
• Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2. — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4.
• Thomas Böhme, Jochen Harant, Michal Tkáč. More than one tough chordal planar graphs are Hamiltonian // Journal of Graph Theory. — 1999. — Т. 32, вип. 4. — С. 405–410. — DOI:10.1002/(SICI)1097-0118(199912)32:4<405::AID-JGT8>3.3.CO;2-Q.
• S. Butler, Ron Graham. Fete of Combinatorics and Computer Science / G. Katona, A. Schrijver, T. Szonyi. — Heidelberg : Springer-Verlag, 2010. — Т. 29. — С. 23–42. — (Bolyai Society Mathematical Studies)
• Wayne Wei-Ming Dai, Masao Sato. IEEE International Symposium on Circuits and Systems. — 1990. — Т. 4. — С. 2677–2681. — DOI:10.1109/ISCAS.1990.112560.
• Erik Demaine, André Schulz. Proc. ACM-SIAM Symposium on Discrete Algorithms. — 2011. — С. 1177–1187.
• Vida Dujmović, Gašper Fijavž, Gwenaël Joret, David R. Wood. The maximum number of cliques in a graph embedded in a surface. — 2009. — arXiv:0906.4142.
• Ehab S. El-Mallah, Charles J. Colbourn. On two dual classes of planar graphs // Discrete Mathematics. — 1990. — Т. 80, вип. 1. — С. 21–40. — DOI:10.1016/0012-365X(90)90293-Q.
• E. W. Elcock, I. Gargantini, T. R. Walsh. Triangular decomposition // Image and Vision Computing. — 1987. — Т. 5, вип. 3. — С. 225–231. — DOI:10.1016/0262-8856(87)90053-9.
• Stefan Felsner, Florian Zickfeld. On the number of planar orientations with prescribed degrees // Electronic Journal of Combinatorics. — 2008. — Т. 15, вип. 1. — С. R77. — arXiv:math/0701771.
• Alan M. Frieze, Charalampos E. Tsourakakis. High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks. — 2011.
• Thomas Fowler. Unique Coloring of Planar Graphs. — Georgia Institute of Technology Mathematics Department, 1998. — (Ph.D. thesis)
• Jim Geelen, Anjie Guo, David McKinnon. Straight line embeddings of cubic planar graphs with integer edge lengths // Journal of Graph Theory. — 2008. — Т. 58, вип. 3. — С. 270–274. — DOI:10.1002/jgt.20304.
• T. Gerlach. Toughness and Hamiltonicity of a class of planar graphs // Discrete Mathematics. — 2004. — Т. 286, вип. 1—2. — С. 61–65. — DOI:10.1016/j.disc.2003.11.046.
• A. Goldner, F. Harary. Note on a smallest nonhamiltonian maximal planar graph // Bull. Malaysian Math. Soc.. — 1975. — Т. 6, вип. 1. — С. 41–42.. См. также журналы 6(2):33 (1975) и 8:104-106 (1977). Посилання взято зі статті Список публікацій Харарі.
• Branko Grünbaum. Unambiguous polyhedral graphs // Israel Journal of Mathematics. — 1963. — Т. 1, вип. 4. — С. 235–238. — DOI:10.1007/BF02759726.
• Branko Grünbaum. Convex Polytopes. — Wiley Interscience, 1967.
• S. L. Hakimi, E. F. Schmeichel. On the number of cycles of length k in a maximal planar graph // Journal of Graph Theory. — 1979. — Т. 3, вип. 1. — С. 69–86. — DOI:10.1002/jgt.3190030108.
• Andrea Jiménez, Marcos Kiwi. Counting perfect matchings of cubic graphs in the geometric dual. — 2010. — arXiv:1010.5918.
• P. Sreenivasa Kumar, C. E. Veni Madhavan. Foundations of Software Technology and Theoretical Computer Science, Ninth Conference, Bangalore, India December 19–21, 1989, Proceedings. — Springer-Verlag, 1989. — Т. 405. — С. 30–43. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-52048-1_30.
• L. Markenzon, C. M. Justel, N. Paciornik. Subclasses of k-trees: Characterization and recognition // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 5. — С. 818–825. — DOI:10.1016/j.dam.2005.05.021.
• Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman, Muhammad Jawaherul Alam. Canadian Conference on Computational Geometry. — 2010.
• J. W. Moon, L. Moser. Simple paths on polyhedra // Pacific Journal of Mathematics. — 1963. — Т. 13. — С. 629–631. — DOI:10.2140/pjm.1963.13.629.
• Rahnuma Islam Nishat, Debajyoti Mondal, Md. Saidur Rahman. Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers. — Springer-Verlag, 2011. — Т. 6502. — С. 317–328. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_29.
• Takao Nishizeki. A 1-tough non-Hamiltonian maximal planar graph // Discrete Mathematics. — 1980. — Т. 30, вип. 3. — С. 305–307. — DOI:10.1016/0012-365X(80)90240-X.
• H. P. Patil. On the structure of k-trees // Journal of Combinatorics, Information and System Sciences. — 1986. — Т. 11, вип. 2—4. — С. 57–64.
• Julius Petersen. Die Theorie der regulären graphs // Acta Mathematica. — 1891. — Т. 15. — С. 193–220. — DOI:10.1007/BF02392606.
• Michael D. Plummer. Extending matchings in planar graphs IV // Discrete Mathematics. — 1992. — Т. 109, вип. 1–3. — С. 207–219. — DOI:10.1016/0012-365X(92)90292-N.
• T. Politof. A characterization and efficient reliability computation of Δ-Y reducible networks. — University of California, Berkeley, 1983. — (Ph.D. thesis). Как процитировано в статье Эль-Маллаха и Колбоурна El-Mallah, Colbourn, (1990).
• Neil Robertson, P. D. Seymour. Graph minors. III. Planar tree-width // Journal of Combinatorial Theory. — 1984. — Т. 36, вип. 1. — С. 49–64. — (Series B). — DOI:10.1016/0095-8956(84)90013-3.
• Fujio Takeo. On triangulated graphs. I // Bull. Fukuoka Gakugei Univ. III. — 1960. — Т. 10. — С. 9–21.. На помилку щодо гамільтоновості в MathSciNet вказав Вільям Татт.
• William Thurston. The geometry and topology of 3-manifolds. — Princeton lecture notes, 1978–1981.
• Charalampos E. Tsourakakis. The Degree Sequence of Random Apollonian Networks. — Department of Mathematical Sciences, Carnegie Mellon University, 2011. — arXiv:1106.1940v1.
• David R. Wood. On the maximum number of cliques in a graph // Graphs and Combinatorics. — 2007. — Т. 23, вип. 3. — С. 337–352. — arXiv:math/0602191. — DOI:10.1007/s00373-007-0738-8.
• Zhongzhi Zhang, Lichao Chen, Shuigeng Zhou, Lujun Fang, Jihong Guan, Tao Zou. Analytical solution of average path length for Apollonian networks // Physical Review E. — 2008. — Т. 77. — С. 017102. — arXiv:0706.3491. — DOI:10.1103/PhysRevE.77.017102.
• Tao Zhou, Gang Yan, Bing-Hong Wang. Maximal planar networks with large clustering coefficient and power-law degree distribution // Physical Review E. — 2005. — Т. 71, вип. 4. — С. 046141. — arXiv:cond-mat/0412448. — DOI:10.1103/PhysRevE.71.046141.
• Tao Zhou, Gang Yan, Pei-Ling Zhou, Zhong-Qian Fu, Bing-Hong Wang. Random Apollonian networks. — University of Science and Technology of China, Hefei Anhui, 2004. — arXiv:cond-mat/0409414v2.
• Florian Zickfeld, Günter M. Ziegler. Workshop on Geometric and Topological Combinatorics. — Alcal ́a de Henares, Madrid, 2006.

Посилання

• Weisstein, Eric W. Сітка Аполлонія(англ.) на сайті Wolfram MathWorld.
• Matlab Simulation Code