Перегляд вихідного коду сторінки Незачеплене вкладення графа

'''Незачеплене вкладення графа'''&nbsp;— [[Вкладення графа|вкладення]] неорієнтованого графа в [[евклідів простір]], за якого жодні два цикли графа не мають ненульового [[Коефіцієнт зачеплення|коефіцієнта зачеплення]]. '''Плоске вкладення'''&nbsp;— вкладення, в якому будь-який цикл є межею топологічного [[круг]]а, [[внутрішність]] якого не зачеплена з графом. '''Граф, що вкладається без зачеплень''',&nbsp;— граф, що має незачеплене або плоске вкладення. Ці графи утворюють тривимірний аналог [[Планарний граф|планарних графів]]{{Sfn|Sachs|1983}}. Напроти, '''суттєво зачеплений граф'''&nbsp;— це граф, який не має незачепленого вкладення.

Плоскі вкладення автоматично не мають зачеплень, але не навпаки{{Sfn|Robertson, Seymour, Thomas|1993a}}. [[Повний граф]] <math>K_6</math>, [[граф Петерсена]] та інші п'ять графів із [[Петерсонове сімейство|петерсенового сімейства графів]] не мають незачеплених вкладень{{Sfn|Sachs|1983}}. Графи, що допускають незачеплене вкладення, замкнені за [[Мінор графа|мінорами графа]]{{Sfn|Nešetřil, Thomas|1985}} і [[Перетворення трикутник-зірка|перетвореннями Y-Δ]]{{Sfn|Robertson, Seymour, Thomas|1993a}}. Вони мають графи петерсенового сімейства [[Характеризація забороненими графами|забороненими мінорами]] {{Sfn|Robertson, Seymour, Thomas|1995}} і включають планарні графи та [[Верхівковий граф|вершинні графи]]{{Sfn|Robertson, Seymour, Thomas|1993a}}. Графи можна розпізнати (а плоске вкладення&nbsp;— побудувати) за [[Часова складність|лінійний час]] {{Sfn|Kawarabayashi, Kreutzer, Mohar|2010}}.

== Визначення ==
[[Файл:Hopf_Link.png|міні| Дві зачеплені криві, що утворюють [[зачеплення Гопфа]]]]
Кажуть, що дві неперетинні криві в [[Евклідів простір|евклідовому просторі]] не зачеплені, якщо існує безперервний рух кривих, який перетворює їх у два незачеплені копланарні кола без проходження однієї кривої через іншу або через себе. Якщо такого безперервного руху немає, кажуть, що криві [[Зачеплення (теорія вузлів)|зачеплені]]. [[Зачеплення Гопфа]], утворене двома колами, які проходять через диск, натягнутий на ці кола, дає найпростіший приклад пари зачеплених кривих, але криві можуть бути зачеплені значно складніше. Якщо криві не зачеплені, можна знайти (топологічний) диск у просторі, обмежений першою кривою, який не перетинається з другого. І тому, якщо такий диск існує, криві не зачеплені.

[[Коефіцієнт зачеплення]] двох замкнутих кривих у тривимірному просторі є [[Топологія|топологічним]] [[Інваріант (математика)|інваріантом]] кривої&nbsp;— це число, визначене для кривих одним з еквівалентних способів, яке не змінюється, якщо рухати криві в просторі безперервно без перетинання одна одної або себе. Коефіцієнт зачеплення знаходять, спроєктувавши вкладення на площину та підрахувавши певним чином числа проходів першої кривої над другою (зі знаком +1 або -1 залежно від напрямку проходу). Проєкція має бути «правильною», що означає, що жодні дві вершини не проєктуються в одну точку, жодна вершина не проєктується всередину ребра і в будь-якій точці проєкції, де ребра перетинаються, вони перетинаються [[Трансверсальність|трансверсально]]. За таких обмежень будь-яка проєкція дає той самий коефіцієнт зачеплення. Коефіцієнт зачеплення незачеплених кривих дорівнює нулю, а тому, якщо пара кривих має ненульовий коефіцієнт зачеплення, дві криві мають бути зачепленими. Однак є приклади зачеплених кривих, що мають нульовий коефіцієнт зачеплення, наприклад, [[зачеплення Вайтгеда]].

Вкладення графа в тривимірний простір складається з відображення вершин графа в точки простору і відображень ребер у криві, так що кожна кінцева точка ребра відображається в кінцеву точку відповідної кривої і криві, що відповідають двом різним ребрам, не перетинаються (хіба що в спільних кінцевих точках). Будь-який скінченний граф має скінченне (можливо експоненціальне) число різних [[Цикл (теорія графів)|простих циклів]], і, якщо граф укладено в тривимірний простір, кожен такий цикл утворює просту замкнуту криву. Можна обчислити коефіцієнт зачеплення кожної пари кривих, що не перетинаються, утворених таким чином. Якщо всі пари циклів мають нульовий коефіцієнт зачеплення, кажуть, що вкладення є незачепленим{{Sfn|Conway, Gordon|1983}}{{Sfn|Sachs|1983}}{{Sfn|Robertson, Seymour, Thomas|1993a}}.

У деяких випадках граф можна вкласти в простір так, що для кожного циклу в графі можна знайти диск, обмежений цим циклом, який не перетинає інших елементів графа. У цьому випадку цикл має бути не зачепленим з іншими циклами графа, що не перетинають його. Кажуть, що вкладення плоске, якщо будь-який цикл обмежує диск у такий спосіб{{Sfn|Robertson, Seymour, Thomas|1993a}}. Аналогічне визначення «хорошого вкладення» наведено в статті Мотвані, Рагунатана та Сарана ({{Sfn0|Motwani, Raghunathan, Saran|1988}}. Див. також {{Harvtxt|Saran|1989}} та {{Harvtxt|Böhme|1990}}.<nowiki></ref></nowiki>. Плоске вкладення обов'язково є незачепленим, але можуть бути незачеплені вкладення, які не є плоскими. Наприклад, якщо ''G''&nbsp;— граф, утворений двома роздільними циклами, і при вкладенні утворюється зачеплення Вайтгеда, вкладення є незачепленим, але не плоским.

Кажуть, що граф суттєво зачеплений, якщо за будь-якого вкладення виходить зачеплене вкладення. Хоча незачеплене і плоске вкладення не те ж саме, графи, які мають незачеплені вкладення, виявляються тими ж графами, що й графи, які мають плоскі вкладення{{Sfn|Robertson, Seymour, Thomas|1993b}}.

== Приклади та контрприклади ==
[[Файл:Petersen_family.svg|міні| [[Петерсонове сімейство|Петерсенове сімейство графів]].]]
Як показав Сакс{{Sfn|Sachs|1983}}, усі сім графів петерсенового сімейства істотно зачеплені, і не має значення, як ці графи вкладені в простір: за будь-якого вкладення вони мають два зачеплених цикли. Ці графи включають [[повний граф]] <math>K_6</math>, [[граф Петерсена]], граф, утворений видаленням ребра з [[Повний двочастковий граф|повного двочасткового графа]] <math>K_{4,4}</math>, і повний тричастковий граф <math>K_{3,3,1}</math>.

Будь-який [[планарний граф]] має плоске і незачеплене вкладення&nbsp;— просто вкладаємо граф у площину, що міститься в (тривимірному) просторі. Якщо граф планарний, це єдиний спосіб укладання графа плоско і незачеплено&nbsp;— будь-яке плоске вкладення можна неперервно деформувати у вкладення на площині. І навпаки, будь-який непланарний незачеплений граф має множинні незачеплені вкладення{{Sfn|Robertson, Seymour, Thomas|1993a}}.
[[Файл:Apex_graph.svg|міні|[[Верхівковий граф]]. Якщо планарну частину графа вкладено в площину, розташовану в просторі, верхівка графа (вершина, що порушує планарність), поміщається над площиною і з'єднується прямими відрізками, і одержане вкладення є плоским.]]
[[Верхівковий граф]], утворений додаванням однієї вершини до планарного графа, також має плоске і незачеплене вкладення&nbsp;— вкладаємо планарну частину графа на площину, поміщаємо верхівку графа (вершина, що порушує планарність) над площиною, а потім проводимо ребра з верхівки в суміжні їй вершини у вигляді відрізків. Будь-яка замкнута крива на площині обмежує диск, який не проходить через інший елемент графа, а будь-яка замкнута крива через верхівку обмежує диск над площиною, який не проходить через будь-який інший елемент графа{{Sfn|Robertson, Seymour, Thomas|1993a}}.

Якщо граф має незачеплене або плоске вкладення, то модифікація графа поділом або об'єднанням його ребер, додаванням або видаленням кратних ребер між парою вершин або проведенням [[Перетворення трикутник-зірка|Y-Δ-перетворень]], за яких вершина степеня три замінюється трикутником, що з'єднує три сусіди, або навпаки, приводить до збереження існування плоского або незачепленого вкладення{{Sfn|Robertson, Seymour, Thomas|1993a}}. Зокрема, в [[Кубічний граф|кубічному]] планарному графі (в якому всі вершини мають рівно три сусіди, як у куба) можна зробити копії будь-якої [[Задача про незалежну множину|незалежної множини]] вершин, здійснивши Y-Δ-перетворення, додавши кратні копії ребер в отриманих трикутниках, а потім здійснивши зворотне Δ-Y-перетворення.

== Характеризація і розпізнавання ==
Якщо граф <math>G</math> має незачеплене або плоске вкладення, то будь-який [[Мінор графа|мінор]] графа <math>G</math> (граф, утворений стягуванням ребер і видаленням ребер і вершин) також має незачеплене або плоске вкладення. Видалення не може зруйнувати можливість незачепленого або плоского вкладення, а стягування можна здійснити, залишивши одну кінцеву точку стягуваного ребра на місці і перемкнувши всі ребра, інцидентні протилежній вершині. Таким чином, за [[Теорема Робертсона — Сеймура|теоремою Робертсона&nbsp;— Сеймура]], графи, що мають незачеплене вкладення, мають [[Характеризація забороненими графами|характеризацію забороненими графами]] як графи, що не містять будь-якого зі скінченного набору мінорів{{Sfn|Nešetřil, Thomas|1985}}.

Множину заборонених мінорів для графів, що допускають незачеплене вкладення, виявив Сакс{{Sfn|Sachs|1983}}&nbsp;— сім графів [[Петерсонове сімейство|петерсенового сімейства]] є мінорно мінімальними істотно зачепленими графами. Однак Сакс не зміг довести, що тільки ці графи є мінорно мінімальними зачепленими графами, і це зробили Робертсон, Сеймур і Томас{{Sfn|Robertson, Seymour, Thomas|1995}}.

Характеризація забороненими мінорами графів, які допускають незачеплене вкладення, веде до алгоритму їх розпізнавання з [[Часова складність|поліноміальним часом роботи]], але при цьому цей алгоритм не будує дійсного вкладення. Каравабайші, Крейцер і Мохар{{Sfn|Kawarabayashi, Kreutzer, Mohar|2010}} описали алгоритм з лінійним часом роботи, який перевіряє, чи вкладаний граф незачеплено, і, якщо вкладаний, будує плоске вкладення графа. Їхній алгоритм знаходить великі планарні підграфи всередині заданого графа, такі, що, якщо існує незачеплене вкладення, вони представляють планарне вкладення підграфа. Повторно спрощуючи граф, коли такий підграф знайдено, вони зводять задачу до задачі, в якій решта графа обмежена [[Деревна ширина (теорія графів)|деревною шириною]], і з цього моменту задачу можна розв'язати за допомогою [[Динамічне програмування|динамічного програмування]].

Задачу ефективної перевірки, чи є задане вкладення плоским або незачепленим, поставили Робертсон, Сеймур і Томас{{Sfn|Robertson, Seymour, Thomas|1993a}}. Задача залишається нерозв'язаною і за складністю еквівалентна [[Задача розв'язування|задачі розв'язування вузла]], задачі перевірки, чи є крива в просторі незавузленою{{Sfn|Kawarabayashi, Kreutzer, Mohar|2010}}. Відомо, що перевірка незавузленості (а отже, й незачепленого вкладення) належить до класу [[Клас складності NP|NP]], але невідомо, чи належить вона до класу [[NP-повна задача|NP-повних]] задач{{Sfn|Hass, Lagarias, Pippenger|1999}}.

== Пов'язані сімейства графів ==
[[Інваріант Колен де Вердьєра]]&nbsp;— це число, визначене для будь-якого графа на основі [[Алгебрична теорія графів|алгебричної теорії графів]]. Граф з інваріантом Колен де Вердьєра, що не перевершує μ, для будь-якої фіксованої сталої μ утворює замкнуте за мінорами сімейство, і кілька перших таких сімейств добре відомі: графи з μ ≤ 1&nbsp;— це лінійні ліси (незв'язне об'єднання шляхів), графи з μ ≤ 2&nbsp;— [[Зовніпланарний граф|зовніпланарні графи]], а графи з μ ≤ 3&nbsp;— [[Планарний граф|планарні графи]]. Як припустили Робертсон, Сеймур і Томас{{Sfn|Robertson, Seymour, Thomas|1993a}} і довели [[Ласло Ловас|Ловас]] і Шрайвер{{Sfn|Lovász, Schrijver|1998}}, графами з μ ≤ 4 точно є графи з незачепленим вкладенням.
[[Файл:Apex_rhombic_dodecahedron.svg|міні|Незачеплений вершинний граф, нескоротний перетворенням YΔY.]]
Планарні графи і [[Верхівковий граф|вершинні графи]] допускають незачеплене вкладення, як і графи, одержувані [[Перетворення трикутник-зірка|Y-Δ перетвореннями]] з них{{Sfn|Robertson, Seymour, Thomas|1993a}}. ''YΔY-скоротні графи''&nbsp;— це графи, які можна звести до однієї вершини перетворенням Y-Δ, видаленням ізольованих і завислих вершин (вершин степеня 1) і заміною дуг при вершині степеня два однією дугою. Ці графи також замкнуті за мінорами. Однак існують незачеплені YΔY-нескоротні графи, такі як верхівковий граф, утворений з'єднанням верхівки (вершини, що порушує планарність) із усіма вершинами степеня три [[ромбододекаедр]]а{{Sfn|Truemper|1992}}. Існують також незачеплені графи, які не можна перетворити за допомогою Y-Δ-перетворень, видаленням ізольованих і завислих вершин і заміною дуг при вершині зі степенем два однією дугою на вершинний граф. Наприклад, [[Корона (теорія графів)|корона]] з десятьма вершинами має незачеплене вкладення, але її не можна перетворити на вершинний граф у зазначений спосіб{{Sfn|Robertson, Seymour, Thomas|1993a}}.

З поняттям незачепленого вкладення пов'язане поняття '''незавузленого вкладення'''. Це таке вкладення графа, що ніякої простий цикл не утворює нетривіального [[Вузол (математика)|вузла]]. До графів, що не мають незавузленого вкладення, належать ''K''<sub>7</sub> і ''K''<sub>3,3,1,1</sub>{{Sfn|Conway, Gordon|1983}}{{Sfn|Foisy|2002}}. Однак існують мінімальні заборонені мінори для незавузлених вкладень, які не утворені (на відміну від зазначених двох графів) доданням однієї вершини до істотно зачепленого графа{{Sfn|Foisy|2003}}.

Можна визначити сімейства графів за наявністю або відсутністю в їх вкладенні складніших вузлів і зачеплень{{Sfn|Nešetřil, Thomas|1985}}{{Sfn|Fleming, Diesl|2005}}, або за незачепленим вкладенням у {{Не перекладено|тривимірний многовид||en|3-manifold}}, відмінний від евклідового простору{{Sfn|Flapan, Howards, Lawrence, Mellor|2006}}. Флапан, Наїмі і Поммершейм{{Sfn|Flapan, Naimi, Pommersheim|2001}} визначили вкладення графа як тричі зачеплене, якщо існують три цикли, жоден з яких не можна відокремити від двох інших. Вони показали, що ''K''<sub>9</sub> не тричі істотно зачеплений, а ''K''<sub>10</sub> зачеплений<ref>Інші приклади не тричі зачеплених графів див. у {{Sfn0|Bowlin, Foisy|2004}}.</ref>. Загальніше, можна визначити ''n''-зачеплене вкладення для будь-якого <math>n</math> як вкладення, що містить <math>n</math>-компонентне зачеплення, яке не можна розділити топологічною сферою на дві окремі частини. Мінорно мінімальні істотно <math>n</math>-зачеплені графи відомі для всіх <math>n</math>{{Sfn|Flapan, Pommersheim, Foisy, Naimi|2001}}.

== Історія ==
Питання, чи має <math>K_6</math> зачеплене або плоске вкладення, поставив на початку [[1970-ті|1970-х]] у [[Топологія|топологічній]] дослідницькій спільноті Боте{{Sfn|Bothe|1973}}. До незачепленого вкладення привернув увагу теоретиків [[Теорія графів|графів]] Сакс{{Sfn|Sachs|1983}}, який запропонував кілька пов'язаних задач, зокрема, задачу пошуку [[Характеризація забороненими графами|характеризації забороненими графами]] графів із незачепленим або плоским вкладенням. Він показав, що сім графів [[Петерсонове сімейство|петерсенового сімейства]] (включно з <math>K_6</math>) не мають таких вкладень. Як помітили Нешетріл і Томас{{Sfn|Nešetřil, Thomas|1985}}, графи, що допускають незацеплене вкладення, [[Замикання (математика)|замкнуті]] за [[Мінор графа|мінорами графа]], звідки за [[Теорема Робертсона — Сеймура|теоремою Робертсона&nbsp;— Сеймура]] випливає, що характеризація забороненими графами існує. Доведення існування скінченного числа перешкоджальних графів не веде до явного опису цієї множини заборонених мінорів, але з результатів Сакса випливає, що сім графів петерсенового сімейства належать до множини. Ці задачі остаточно розв'язали Робертсон, Сеймур і Томас{{Sfn|Robertson, Seymour, Thomas|1995}}{{Sfn|Robertson, Seymour, Thomas|1993b}}, які показали, що ці сім графів петерсенового сімейства є єдиними мінімальними забороненими мінорами для таких графів. Таким чином, незачеплено вкладені графи і плоско вкладені графи є однією й тією ж множиною графів і обидва сімейства можна визначити як графи, що не містять елементів сімейства Петерсена як мінорів.

Сакс{{Sfn|Sachs|1983}} також поставив питання про межі числа ребер і [[Розфарбовування графів|хроматичного числа]] вкладаних без зачеплення графів. Число ребер у вкладаному без зачеплення графі з <math>n</math> вершинами не перевищує <math>4 n - 10</math>&nbsp;— [[Максимальні та мінімальні елементи|максимальні]] [[Верхівковий граф|верхівкові графи]] з <math>n > 4</math> мають рівно таке число ребер{{Sfn|Sachs|1983}}, а Мадер{{Sfn|Mader|1968}} довів правильність верхньої межі для загальнішого класу вільних від ''K''<sub>6</sub> мінорів графів. 1985 року показано, що питання Сакса про хроматичне число було б вирішене, якби було доведено [[Гіпотеза Хадвігера|гіпотезу Хадвігера]], що будь-який <math>k</math>-хроматичний граф має в як мінор повний граф з <math>k</math> вершинами{{Sfn|Nešetřil, Thomas|1985}}. Доведення Робертсона, Сеймура і Томаса{{Sfn|Robertson, Seymour, Thomas|1993c}} випадку <math>k = 6</math> гіпотези Хадвігера достатньо для вирішення питання Сакса&nbsp;— графи без зачеплень можна розфарбувати максимум п'ятьма кольорами, оскільки будь-який 6-хроматичний граф містить мінор <math>K_6</math> і не є незачепленим, і існують незачеплені графи, такі як <math>K_5</math>, що вимагають п'яти кольорів. Із [[Снарк (теорія графів)|теореми про снарки]] випливає, що будь-який [[Кубічний граф|кубічний]] вкладений без зачеплення граф є [[Розфарбовування ребер|реберно розфарбовуваним у 3 кольори]].

Вивчення вкладень без зачеплень почалося наприкінці 1980-х років під час дослідження [[алгоритм]]ів{{Sfn|Fellows, Langston|1988}}{{Sfn|Motwani, Raghunathan, Saran|1988}}. Алгоритмічно задачу розпізнавання вкладених без зачеплень і плоско вкладених графів розв'язано, коли було доведено характеризацію забороненими мінорами&nbsp;— алгоритм Робертсона і Сеймура{{Sfn|Robertson, Seymour|1995}} можна використати для перевірки за [[Часова складність|поліноміальний час]], чи містить заданий граф будь-який із семи заборонених мінорів<ref>Застосовність алгоритму Робертсона&nbsp;— Сеймура до цієї задачі помітили Феллоус і Лангстон ({{Sfn0|Fellows, Langston|1988}}).</ref>. Цей метод не будує незачепленого або плоского вкладення, якщо воно існує, але ван дер Голст (Hein van der Holst) запропонував алгоритм, який будує вкладення{{Sfn|van der Holst|2009}}, а пізніше знайдено ефективніший алгоритм, що працює за [[Часова складність|лінійний час]]{{Sfn|Kawarabayashi, Kreutzer, Mohar|2010}}.

На останнє питання Сакса{{Sfn|Sachs|1983}} про можливість аналогії [[Теорема Фарі про розпрямлення графа|теореми Фарі]] для незачеплених графів відповіді поки немає. Питання ставиться так: коли існування незачепленого або плоского вкладення з кривими або [[Кусково-лінійна функція|кусково-лінійними]] ребрами тягне існування незачепленого або плоского вкладення, в якому ребра є [[Відрізок|відрізками]]?

== Примітки ==
{{примітки|2}}

== Література ==
{{refbegin}}
* {{Книга
|автор = Thomas Böhme
|ref = Böhme
|відповідальний = Rainer Bodendieck
|ISBN = 978-3-411-14301-6
|місце = Mannheim
|сторінки = 151–167
|видавництво = Bibliographisches Institut, Wissenschaftsverlag
|назва = Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner
|рік = 1990
}}. Як процитировано в книзі Робертсона, Сеймура, Томаса ({{Sfn0|Robertson, Seymour, Thomas|1993a}}).
* {{Стаття|author=H.-G. Bothe|ref=Bothe|серія=New Scottish Book,|видання=Colloquium Mathematicum|pages=163|title=Problem P855|том=28|рік=1973}}. Як процитировано в книзі Сакса ({{Harvtxt|Sachs|1983}}).
* {{Стаття|author=Garry Bowlin, Joel Foisy|ref=Bowlin, Foisy|doi=10.1142/S0218216504003652|issue=8|видання=Journal of Knot Theory and its Ramifications|pages=1021–1028|title=Some new intrinsically 3-linked graphs|том=13|рік=2004}}
* {{Стаття|author=John H. Conway, Cameron McA. Gordon|ref=Conway, Gordon|doi=10.1002/jgt.3190070410|issue=4|видання=[[Journal of Graph Theory]]|pages=445–453|title=Knots and links in spatial graphs|url=https://archive.org/details/sim_journal-of-graph-theory_winter-1983_7_4/page/445|том=7|рік=1983}}
* {{Стаття|author=Michael R. Fellows, Michael A. Langston|ref=Fellows, Langston|doi=10.1145/44483.44491|issue=3|видання=[[Journal of the ACM]]|pages=727–739|title=Nonconstructive tools for proving polynomial-time decidability|том=35|рік=1988}}
* {{Стаття|author=Erica Flapan, Hugh Howards, Don Lawrence, Blake Mellor|ref=Flapan, Howards, Lawrence, Mellor|doi=10.2140/agt.2006.6.1025|видання=[[Algebraic & Geometric Topology]]|pages=1025–1035|title=Intrinsic linking and knotting of graphs in arbitrary 3–manifolds|том=6|рік=2006|arxiv=math/0508004}}
* {{Стаття|author=Erica Flapan, Ramin Naimi, James Pommersheim|ref=Flapan, Naimi, Pommersheim|doi=10.1016/S0166-8641(00)00064-X|issue=2|видання=[[Topology and its Applications]]|pages=239–246|title=Intrinsically triple linked complete graphs|url=http://pages.pomona.edu/~elf04747/Research/I3L.pdf|том=115|рік=2001}}
* {{Стаття|author=Erica Flapan, James Pommersheim, Joel Foisy, Ramin Naimi|ref=Flapan, Pommersheim, Foisy, Naimi|doi=10.1142/S0218216501001360|issue=8|видання=[[Journal of Knot Theory and Its Ramifications]]|pages=1143–1154|title=Intrinsically n-linked graphs|том=10|рік=2001}}.
* {{Стаття|author=Thomas Fleming, Alexander Diesl|ref=Fleming, Diesl|видання=[[Algebraic & Geometric Topology]]|pages=1419–1432|title=Intrinsically linked graphs and even linking number|том=5|рік=2005|arxiv=math/0511133|doi=10.2140/agt.2005.5.1419}}
* {{Стаття|author=Joel Foisy|ref=Foisy|doi=10.1002/jgt.10017|issue=3|видання=[[Journal of Graph Theory]]|pages=178–187|title=Intrinsically knotted graphs|url=https://archive.org/details/sim_journal-of-graph-theory_2002-03_39_3/page/178|том=39|рік=2002}}
* {{Стаття|author=Joel Foisy|ref=Foisy|doi=10.1002/jgt.10114|issue=3|видання=[[Journal of Graph Theory]]|pages=199–209|title=A newly recognized intrinsically knotted graph|url=https://archive.org/details/sim_journal-of-graph-theory_2003-07_43_3/page/199|том=43|рік=2003}}
* {{Стаття|author=Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger|ref=Hass, Lagarias, Pippenger|doi=10.1145/301970.301971|issue=2|видання=[[Journal of the ACM]]|pages=185–211|title=The computational complexity of knot and link problems|том=46|рік=1999|arxiv=math/9807016}}
* {{Стаття|author=Hein van der Holst|ref=van der Holst|doi=10.1016/j.jctb.2008.10.002|issue=2|видання=[[Journal of Combinatorial Theory, Series B]]|pages=512–530|title=A polynomial-time algorithm to find a linkless embedding of a graph|том=99|рік=2009}}
* {{Книга
|автор = Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar
|ref = Kawarabayashi, Kreutzer, Mohar
|doi = 10.1145/1810959.1810975
|сторінки = 97–106
|назва = Proc. ACM Symposium on Computational Geometry (SoCG '10)
|рік = 2010
}}
* {{Стаття|author=László Lovász, Alexander Schrijver|ref=Lovász, Schrijver|doi=10.1090/S0002-9939-98-04244-0|issue=5|видання=[[Proceedings of the American Mathematical Society]]|pages=1275–1285|title=A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs|том=126|рік=1998}}
* {{Стаття|author=W. Mader|ref=Mader|doi=10.1007/BF01350657|issue=2|видання=[[Mathematische Annalen]]|pages=154–168|title=Homomorphiesätze für Graphen|том=178|рік=1968}}
* {{Книга
|автор = Rajeev Motwani, Arvind Raghunathan, Huzur Saran
|ref = Motwani, Raghunathan, Saran
|doi = 10.1109/SFCS.1988.21956
|сторінки = 398–409
|назва = Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS '88)
|рік = 1988
}}
* {{Стаття|author=Jaroslav Nešetřil, Robin Thomas|ref=Nešetřil, Thomas|issue=4|видання=Commentationes Mathematicae Universitatis Carolinae|pages=655–659|title=A note on spatial representation of graphs|url=http://dspace.dml.cz/handle/10338.dmlcz/106404|том=26|рік=1985|archiveurl=https://web.archive.org/web/20110718171201/http://dspace.dml.cz/handle/10338.dmlcz/106404|archivedate=2011-07-18}}
* {{Стаття|author=Neil Robertson, Paul Seymour|ref=Robertson, Seymour|doi=10.1006/jctb.1995.1006|issue=1|видання=[[Journal of Combinatorial Theory, Series B]]|pages=65–110|title=Graph Minors. XIII. The disjoint paths problem|том=63|рік=1995}}
* {{Книга
|автор = Neil Robertson, Paul Seymour, Robin Thomas
|ref = Robertson, Seymour, Thomas
|сторінки = 125–136
|видавництво = American Mathematical Society
|серія = Contemporary Mathematics
|назва = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
|посилання = http://people.math.gatech.edu/~thomas/PAP/linklsurvey.pdf
|том = 147
|рік = 1993a
}}
* {{Стаття|author=Neil Robertson, Paul Seymour, Robin Thomas|ref=Robertson, Seymour, Thomas|doi=10.1090/S0273-0979-1993-00335-5|issue=1|видання=[[Bulletin of the American Mathematical Society]]|pages=84–89|title=Linkless embeddings of graphs in 3-space|том=28|рік=1993b|arxiv=math/9301216}}.
* {{Стаття|author=Neil Robertson, Paul Seymour, Robin Thomas|ref=Robertson, Seymour, Thomas|doi=10.1006/jctb.1995.1032|issue=2|видання=[[Journal of Combinatorial Theory, Series B]]|pages=185–227|title=Sachs' linkless embedding conjecture|том=64|рік=1995}}.
* {{Стаття|author=Neil Robertson, Paul Seymour, Robin Thomas|ref=Robertson, Seymour, Thomas|doi=10.1007/BF01202354|issue=3|видання=[[Combinatorica]]|pages=279–361|title=Hadwiger's conjecture for ''K''<sub>6</sub>-free graphs|url=http://people.math.gatech.edu/~thomas/PAP/hadwiger.pdf|том=13|рік=1993c}}.
* {{Книга
|автор = Horst Sachs
|ref = Sachs
|назва = On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem
|doi = 10.1007/BFb0071633
|відповідальний = M. Horowiecki, J. W. Kennedy, M. M. Sysło
|сторінки = 230–241
|видавництво = Springer-Verlag
|серія = Lecture Notes in Mathematics
|видання = Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981
|том = 1018
|рік = 1983
}}.
* {{Книга
|автор = Huzur Saran
|ref = Saran
|видавництво = University of California, Berkeley
|серія = Ph.D. thesis
|назва = Constructive Results in Graph Minors: Linkless Embeddings
|рік = 1989
}}.
* {{Книга
|автор = Klaus Truemper
|ref = Truemper
|сторінки = 100–101
|видавництво = Academic Press
|назва = Matroid Decomposition
|посилання = http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf
|рік = 1992
}}.
* {{Стаття|author=J. L. Ramírez Alfonsín|title=Knots and links in spatial graphs: a survey|видання=Discrete Mathematics|рік=2005|том=302|issue=1–3|pages=225–242|doi=10.1016/j.disc.2004.07.035}}
{{Refend}}

[[Категорія:Теорія мінорів графів]]
[[Категорія:Теорія вузлів]]
[[Категорія:Топологічна теорія графів]]