Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В теорії графів зовніпланарний граф це граф що допускає планарну діаграму в якій усі вершини належать зовнішній грані Ма

Зовніпланарний граф

Зовніпланарний граф

В теорії графів зовніпланарний граф — це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані.

image
Максимальний зовніпланарний граф і його 3-розмальовка.
image
Повний граф K4 є найменшим планарним графом, який не є зовніпланарним.

Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження і деревну ширину не більше 2.

Зовніпланарні графи є підмножиною планарних графів, підграфами паралельно-послідовних графів і колових графів. Максимальний зовніпланарний граф — це граф, до якого можна додати ребро без втрати зовніпланарності. Вони також є хордальними і .

Історія

Зовніпланарні графи вперше вивчали і назвали Шартран і Харарі, розглядаючи задачу визначення планарності графів, утворених за допомогою досконалих парувань, що зв'язують дві копії базового графа (наприклад, багато з узагальнених графів Петерсена утворено цим способом з двох копій графа-циклу). Вони показали, якщо базовий граф двозв'язний, граф, отриманий з нього описаним способом, планарний тоді й лише тоді, коли базовий граф зовніпланарний і парування утворює діедральні перестановки зовнішнього циклу.

Визначення та опис

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

Максимальний зовніпланарний граф — це зовніпланарний граф, до якого можна додати будь-яке ребро, не порушивши властивість зовніпланарності. Будь-який максимальний зовніпланарний граф з n вершинами має в рівно 2n − 3 ребер і будь-яка обмежена грань максимального зовніпланарного графа є трикутником.

Заборонені графи

Докладніше: Характеризація забороненими графами

Зовніпланарні графи мають характеризацію забороненими графами, аналогічну теоремі Понтрягіна — Куратовського і теоремі Вагнера для планарних графів — граф зовніпланарний тоді й лише тоді, коли він не містить підрозбиття повного графа K4 або повного двочасткового графа K2,3. Альтернативно, граф зовніпланарний тоді й лише тоді, коли він не містить K4 або K2,3 як мінор графа, отриманого видаленням і стягуванням ребер.

Граф без трикутників зовніпланарний тоді й лише тоді, коли він не містить підрозділів K2,3.

Інваріант Колена де Вердьєра

Докладніше: Інваріант Колен де Вердьєра

Граф зовніпланарний тоді й лише тоді, коли його не перевищує двох. Графи, що характеризуються подібним чином за значенням інваріанта Колена де Вердьєра (який не перевершує значення 1, 3 або 4) — це лінійні ліси, планарні графи і вклада́нні без зачеплення графи.

Властивості

Двозв'язність і гамільтоновість

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

Будь-який максимальний зовніпланарний граф задовольняє сильнішим умовам, ніж гамільтоновість — він вершинно панциклічний, що означає, що для будь-якої вершини v і будь-якого числа k в інтервалі від трьох до числа вершин графа існує цикл довжини k, що містить v. Цикл такої довжини можна знайти послідовним видаленням трикутників, сполучених з залишком графа єдиним ребром, таких, що вилучена вершина не збігається з v, поки зовнішня грань решти графа не набуде довжини k.

Планарний граф є зовніпланарним тоді й лише тоді, коли всі його двозв'язні компоненти зовніпланарні.

Розмальовка

Всі зовніпланарні графи без петель можна розфарбувати всього трьома кольорами. Цей факт проявляється помітно у спрощеному доведенні теореми про картинну галерею Хватала Фіском. Розмальовку трьома кольорами можна знайти за лінійний час алгоритмом жадібного розмальовування, який видаляє будь-яку вершину зі степенем, що не перевищує двох, і розфарбовує решту графа рекурсивно, а потім повертає кожну з видалених вершин з кольором, відмінним від кольорів двох її сусідів.

За теоремою Візінга хроматичний індекс будь-якого графа (мінімальне число кольорів, необхідних для розфарбовування ребер графа так, що ніякі два суміжних ребра не мають одного кольору) дорівнює або на одиницю більший від найбільшого зі степенів вершин графа. Для зовніпланарних графів хроматичний індекс дорівнює найбільшому степеню, якщо тільки граф не є циклом непарної довжини. Реберну розмальовку з оптимальним числом кольорів можна знайти за лінійний час на основі пошуку в ширину слабкого двоїстого дерева.

Інші властивості

Зовніпланарні графи мають виродження, яке не перевершує 2 — будь-який підграф зовніпланарного графа містить вершину зі степенем, що не перевершує 2.

Зовніпланарні графи мають деревну ширину, що не перевищує 2, звідки випливає, що багато задач оптимізації на графах, які NP-повні для графів загального вигляду, можна розв'язати за поліноміальний час за допомогою динамічного програмування, якщо входом служить зовніпланарний граф. Загальніше, k-зовніпланарний граф має деревну ширину O(k).

Будь-який зовніпланарний граф можна подати у вигляді графа перетинів прямокутників із паралельними осям сторонами, так що зовніпланарні графи мають інтервальну розмірність максимум два.

Пов'язані родини графів

image
Кактус. Кактуси утворюють підклас зовніпланарних графів.

Будь-який зовніпланарний граф є планарним. Будь-який зовніпланарний граф є підграфом паралельно-послідовного графа. Однак не всі паралельно-послідовні графи зовніпланарні. Повний дводольний граф K2,3 є планарним і паралельно-послідовним, але не зовніпланарним. З іншого боку, повний граф K4 планарний, але ні паралельно-послідовний, ні зовніпланарний. Будь-який ліс і будь-який кактус зовніпланарні.

Слабко двоїстий планарний граф вкладеного зовніпланарного графа (граф, що має на вершині для кожної обмеженої грані вкладення і по ребру для суміжних обмежених граней) є лісом, а слабко двоїстий планарний граф графа Халіна є зовніпланарним графом. Планарний граф є зовніпланарним тоді й лише тоді, коли його слабко двоїстий граф є лісом, і граф є графом Халіна тоді й лише тоді, коли його слабко двоїстий граф є двозв'язним і зовніпланарним.

Існує поняття ступеня зовніпланарності. 1-зовніпланарне вкладення графа — це те ж саме, що зовніпланарне вкладення. Для k > 1 кажуть, що планарне вкладення є k-зовніпланарним, якщо видалення вершини з зовнішньої грані призводить до (k − 1)-зовніпланарного вкладення. Граф є k-зовніпланарним тоді й лише тоді, коли він має k-зовніпланарне вкладення.

Будь-який максимальний зовніпланарний граф є хордальним графом. Будь-який максимальний зовніпланарний граф є простого багатокутника. Максимальні зовніпланарні графи утворюються як графи тріангуляції багатокутників. Вони є також прикладами 2-дерев, паралельно-послідовних графів і хордальних графів.

Будь-який зовніпланарний граф є коловим графом, графом перетинів множини хорд кола.

Примітки

  1. Chartrand, Harary, 1967.
  2. Felsner, 2004.
  3. Chartrand, Harary, (1967); Sysło, (1979); Brandstädt, Le, Spinrad, (1999), Proposition 7.3.1, p. 117; Felsner, (2004).
  4. Diestel, 2000.
  5. Sysło, 1979.
  6. Li, Corneil, Mendelsohn, 2000, с. Proposition 2.5.
  7. Proskurowski, Sysło, 1986.
  8. Fisk, 1978.
  9. Fiorini, 1975.
  10. Lick, White, 1970.
  11. Baker, 1994.
  12. Визначення інтервальної розмірності графа можна знайти в книзі Робертса. Англійська назва терміна — boxicity.
  13. Робертс, 1986, с. 129.
  14. Scheinerman, 1984.
  15. Brandstädt, Le, Spinrad, 1999, с. 54.
  16. Brandstädt, Le, Spinrad, 1999, с. 174.
  17. Sysło, Proskurowski, 1983.
  18. Kane, Basu, 1976.
  19. El-Gindy, (1985); Lin, Skiena, (1995); Brandstädt, Le, Spinrad, (1999), Theorem 4.10.3, p. 65.
  20. Wessel, Pöschel, 1985.
  21. Unger, 1988.

Література

  • Ф.С.Робертс. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. — Москва : «Наука», 1986. — С. 129. — (Теория и методы системного анализа)
  • Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs // . — 1994. — Т. 41, вип. 1 (17 червня). — С. 153–180. — DOI:10.1145/174644.174650..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. The problem of outer embeddings in pseudosurfaces // [en]. — 2004. — Т. 71 (17 червня). — С. 79–91..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. Obstruction sets for outer-bananas-surface graphs // [en]. — 2004. — Т. 73 (17 червня). — С. 65–77..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. Uncountable graphs with all their vertices in one face // . — 2006. — Т. 112 (4) (17 червня). — С. 307–313. — DOI:10.1007/s10474-006-0082-0..
  • Luis Boza, Eugenio M. Fedriani, Juan Núñez. Outer-embeddability in certain pseudosurfaces arising from three spheres // . — 2010. — Т. 310 (17 червня). — С. 3359–3367. — DOI:10.1016/j.disc.2010.07.027..
  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — Society for Industrial and Applied Mathematics, 1999. — (SIAM Monographs on Discrete Mathematics and Applications) — ..
  • Gary Chartrand, Frank Harary. Planar permutation graphs // Annales de l'Institut Henri Poincaré B. — 1967. — Т. 3, вип. 4 (17 червня). — С. 433–438. з джерела 20 січня 2022. Процитовано 25 листопада 2020..
  • Reinhard Diestel. Graph Theory. — Springer-Verlag, 2000. — Т. 173. — С. 107. — () — ..
  • H. El-Gindy. Hierarchical decomposition of polygons with applications. — McGill University, 1985. — (Ph.D. thesis). Як процитовано у Брандштедта, Лі і Спінрада (Brandstädt, Le та Spinrad, (1999)).
  • Stefan Felsner. Geometric graphs and arrangements: some chapters from combinational geometry. — Vieweg+Teubner Verlag, 2004. — С. 6. — ..
  • Stanley Fiorini. On the chromatic index of outerplanar graphs // . — 1975. — Т. 18, вип. 1 (17 червня). — С. 35–38. — (Series B). — DOI:10.1016/0095-8956(75)90060-X..
  • Steve Fisk. A short proof of Chvátal's watchman theorem // . — 1978. — Т. 24 (17 червня). — С. 374. — (Series B). — DOI:10.1016/0095-8956(78)90059-X..
  • Herbert J. Fleischner, D. P. Geller, Frank Harary. Outerplanar graphs and weak duals // Journal of the Indian Mathematical Society. — 1974. — Т. 38 (17 червня). — С. 215–219..
  • Vinay G. Kane, Sanat K. Basu. On the depth of a planar graph // . — 1976. — Т. 14, вип. 1 (17 червня). — С. 63–67. — DOI:10.1016/0012-365X(76)90006-6..
  • Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyclicity and NP-completeness in planar graphs // . — 2000. — Т. 98, вип. 3 (17 червня). — С. 219–225. — DOI:10.1016/S0166-218X(99)00163-8..
  • Don R. Lick, Arthur T. White. k-degenerate graphs // . — 1970. — Т. 22 (17 червня). — С. 1082–1096. — DOI:10.4153/CJM-1970-125-1. з джерела 23 липня 2012. Процитовано 25 листопада 2020..
  • Yaw-Ling Lin, Steven S. Skiena. Complexity aspects of visibility graphs // . — 1995. — Т. 5, вип. 3 (17 червня). — С. 289–312. — DOI:10.1142/S0218195995000179..
  • Andrzej Proskurowski, Maciej M. Sysło. Efficient vertex-and edge-coloring of outerplanar graphs // SIAM Journal on Algebraic and Discrete Methods. — 1986. — Т. 7 (17 червня). — С. 131–136. — DOI:10.1137/0607016..
  • E. R. Scheinerman. Intersection Classes and Multiple Intersection Parameters of a Graph. — Princeton University, 1984. — (Ph.D. thesis). As cited by Brandstädt, Le та Spinrad, (1999).
  • Maciej M. Sysło. Characterizations of outerplanar graphs // . — 1979. — Т. 26, вип. 1 (17 червня). — С. 47–53. — DOI:10.1016/0012-365X(79)90060-8..
  • Maciej M. Sysło, Andrzej Proskurowski. Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 248–256. — () — DOI:10.1007/BFb0071635..
  • Walter Unger. Proc. 5th (STACS '88). — Springer-Verlag, 1988. — Т. 294. — С. 61–72. — () — DOI:10.1007/BFb0035832..
  • W. Wessel, R. Pöschel. Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984 / Horst Sachs. — B.G. Teubner, 1985. — Т. 73. — С. 207–210. — (Teubner-Texte zur Mathematik). Як процитував Унгер (Unger, (1988)).

Посилання

  • ,
  • Weisstein, Eric W. Зовніпланарний граф(англ.) на сайті Wolfram MathWorld.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V teoriyi grafiv zovniplanarnij graf ce graf sho dopuskaye planarnu diagramu v yakij usi vershini nalezhat zovnishnij grani Maksimalnij zovniplanarnij graf i jogo 3 rozmalovka Povnij graf K4 ye najmenshim planarnim grafom yakij ne ye zovniplanarnim Zovniplanarni grafi mozhna sharakterizuvati analogichno teoremi Vagnera dlya planarnih grafiv dvoma zaboronenimi minorami K4 i K2 3 abo yih invariantami Kolen de Verdyera Ci grafi mayut gamiltonovi cikli todi j lishe todi koli voni dvozv yazni i v comu vipadku zovnishnya gran utvoryuye yedinij gamiltoniv cikl Bud yakij zovniplanarnij graf mozhna rozfarbuvati v 3 kolori i vin maye virodzhennya i derevnu shirinu ne bilshe 2 Zovniplanarni grafi ye pidmnozhinoyu planarnih grafiv pidgrafami paralelno poslidovnih grafiv i kolovih grafiv Maksimalnij zovniplanarnij graf ce graf do yakogo mozhna dodati rebro bez vtrati zovniplanarnosti Voni takozh ye hordalnimi i IstoriyaZovniplanarni grafi vpershe vivchali i nazvali Shartran i Harari rozglyadayuchi zadachu viznachennya planarnosti grafiv utvorenih za dopomogoyu doskonalih paruvan sho zv yazuyut dvi kopiyi bazovogo grafa napriklad bagato z uzagalnenih grafiv Petersena utvoreno cim sposobom z dvoh kopij grafa ciklu Voni pokazali yaksho bazovij graf dvozv yaznij graf otrimanij z nogo opisanim sposobom planarnij todi j lishe todi koli bazovij graf zovniplanarnij i paruvannya utvoryuye diedralni perestanovki zovnishnogo ciklu Viznachennya ta opisZovniplanarnij graf ye neoriyentovanim grafom yakij mozhna namalyuvati na ploshini bez shreshen takim chinom sho vsi vershini nalezhatimut zovnishnij neobmezhenij grani malyunka Tobto zhodna z vershin ne otochena povnistyu rebrami Alternativno graf G zovniplanarnij yaksho graf utvorenij z G dodavannyam novoyi vershini z yednanoyi rebrami z usima inshimi vershinami planarnij Maksimalnij zovniplanarnij graf ce zovniplanarnij graf do yakogo mozhna dodati bud yake rebro ne porushivshi vlastivist zovniplanarnosti Bud yakij maksimalnij zovniplanarnij graf z n vershinami maye v rivno 2n 3 reber i bud yaka obmezhena gran maksimalnogo zovniplanarnogo grafa ye trikutnikom Zaboroneni grafi Dokladnishe Harakterizaciya zaboronenimi grafami Zovniplanarni grafi mayut harakterizaciyu zaboronenimi grafami analogichnu teoremi Pontryagina Kuratovskogo i teoremi Vagnera dlya planarnih grafiv graf zovniplanarnij todi j lishe todi koli vin ne mistit pidrozbittya povnogo grafa K4 abo povnogo dvochastkovogo grafa K2 3 Alternativno graf zovniplanarnij todi j lishe todi koli vin ne mistit K4 abo K2 3 yak minor grafa otrimanogo vidalennyam i styaguvannyam reber Graf bez trikutnikiv zovniplanarnij todi j lishe todi koli vin ne mistit pidrozdiliv K2 3 Invariant Kolena de Verdyera Dokladnishe Invariant Kolen de Verdyera Graf zovniplanarnij todi j lishe todi koli jogo ne perevishuye dvoh Grafi sho harakterizuyutsya podibnim chinom za znachennyam invarianta Kolena de Verdyera yakij ne perevershuye znachennya 1 3 abo 4 ce linijni lisi planarni grafi i vklada nni bez zacheplennya grafi VlastivostiDvozv yaznist i gamiltonovist Zovniplanarnij graf ye dvozv yaznim todi j lishe todi koli zovnishnya gran utvoryuye prostij cikl bez povtorennya vershin Zovniplanarnij graf ye gamiltonovim todi j lishe todi koli vin dvozv yaznij U comu vipadku zovnishnya gran utvoryuye yedinij gamiltoniv cikl Zagalnishe rozmir najdovshogo ciklu v zovniplanarnomu grafi dorivnyuye chislu vershin najbilshoyi dvozv yaznoyi komponenti Z ciyeyi prichini poshuk gamiltonovih cikliv i najdovshih cikliv u zovniplanarnih grafah mozhna zdijsniti za linijnij chas na protivagu do NP povnoti cih zadach dlya dovilnih grafiv Bud yakij maksimalnij zovniplanarnij graf zadovolnyaye silnishim umovam nizh gamiltonovist vin vershinno panciklichnij sho oznachaye sho dlya bud yakoyi vershini v i bud yakogo chisla k v intervali vid troh do chisla vershin grafa isnuye cikl dovzhini k sho mistit v Cikl takoyi dovzhini mozhna znajti poslidovnim vidalennyam trikutnikiv spoluchenih z zalishkom grafa yedinim rebrom takih sho viluchena vershina ne zbigayetsya z v poki zovnishnya gran reshti grafa ne nabude dovzhini k Planarnij graf ye zovniplanarnim todi j lishe todi koli vsi jogo dvozv yazni komponenti zovniplanarni Rozmalovka Vsi zovniplanarni grafi bez petel mozhna rozfarbuvati vsogo troma kolorami Cej fakt proyavlyayetsya pomitno u sproshenomu dovedenni teoremi pro kartinnu galereyu Hvatala Fiskom Rozmalovku troma kolorami mozhna znajti za linijnij chas algoritmom zhadibnogo rozmalovuvannya yakij vidalyaye bud yaku vershinu zi stepenem sho ne perevishuye dvoh i rozfarbovuye reshtu grafa rekursivno a potim povertaye kozhnu z vidalenih vershin z kolorom vidminnim vid koloriv dvoh yiyi susidiv Za teoremoyu Vizinga hromatichnij indeks bud yakogo grafa minimalne chislo koloriv neobhidnih dlya rozfarbovuvannya reber grafa tak sho niyaki dva sumizhnih rebra ne mayut odnogo koloru dorivnyuye abo na odinicyu bilshij vid najbilshogo zi stepeniv vershin grafa Dlya zovniplanarnih grafiv hromatichnij indeks dorivnyuye najbilshomu stepenyu yaksho tilki graf ne ye ciklom neparnoyi dovzhini Rebernu rozmalovku z optimalnim chislom koloriv mozhna znajti za linijnij chas na osnovi poshuku v shirinu slabkogo dvoyistogo dereva Inshi vlastivosti Zovniplanarni grafi mayut virodzhennya yake ne perevershuye 2 bud yakij pidgraf zovniplanarnogo grafa mistit vershinu zi stepenem sho ne perevershuye 2 Zovniplanarni grafi mayut derevnu shirinu sho ne perevishuye 2 zvidki viplivaye sho bagato zadach optimizaciyi na grafah yaki NP povni dlya grafiv zagalnogo viglyadu mozhna rozv yazati za polinomialnij chas za dopomogoyu dinamichnogo programuvannya yaksho vhodom sluzhit zovniplanarnij graf Zagalnishe k zovniplanarnij graf maye derevnu shirinu O k Bud yakij zovniplanarnij graf mozhna podati u viglyadi grafa peretiniv pryamokutnikiv iz paralelnimi osyam storonami tak sho zovniplanarni grafi mayut intervalnu rozmirnist maksimum dva Pov yazani rodini grafivKaktus Kaktusi utvoryuyut pidklas zovniplanarnih grafiv Bud yakij zovniplanarnij graf ye planarnim Bud yakij zovniplanarnij graf ye pidgrafom paralelno poslidovnogo grafa Odnak ne vsi paralelno poslidovni grafi zovniplanarni Povnij dvodolnij graf K2 3 ye planarnim i paralelno poslidovnim ale ne zovniplanarnim Z inshogo boku povnij graf K4 planarnij ale ni paralelno poslidovnij ni zovniplanarnij Bud yakij lis i bud yakij kaktus zovniplanarni Slabko dvoyistij planarnij graf vkladenogo zovniplanarnogo grafa graf sho maye na vershini dlya kozhnoyi obmezhenoyi grani vkladennya i po rebru dlya sumizhnih obmezhenih granej ye lisom a slabko dvoyistij planarnij graf grafa Halina ye zovniplanarnim grafom Planarnij graf ye zovniplanarnim todi j lishe todi koli jogo slabko dvoyistij graf ye lisom i graf ye grafom Halina todi j lishe todi koli jogo slabko dvoyistij graf ye dvozv yaznim i zovniplanarnim Isnuye ponyattya stupenya zovniplanarnosti 1 zovniplanarne vkladennya grafa ce te zh same sho zovniplanarne vkladennya Dlya k gt 1 kazhut sho planarne vkladennya ye k zovniplanarnim yaksho vidalennya vershini z zovnishnoyi grani prizvodit do k 1 zovniplanarnogo vkladennya Graf ye k zovniplanarnim todi j lishe todi koli vin maye k zovniplanarne vkladennya Bud yakij maksimalnij zovniplanarnij graf ye hordalnim grafom Bud yakij maksimalnij zovniplanarnij graf ye prostogo bagatokutnika Maksimalni zovniplanarni grafi utvoryuyutsya yak grafi triangulyaciyi bagatokutnikiv Voni ye takozh prikladami 2 derev paralelno poslidovnih grafiv i hordalnih grafiv Bud yakij zovniplanarnij graf ye kolovim grafom grafom peretiniv mnozhini hord kola PrimitkiChartrand Harary 1967 Felsner 2004 Chartrand Harary 1967 Syslo 1979 Brandstadt Le Spinrad 1999 Proposition 7 3 1 p 117 Felsner 2004 Diestel 2000 Syslo 1979 Li Corneil Mendelsohn 2000 s Proposition 2 5 Proskurowski Syslo 1986 Fisk 1978 Fiorini 1975 Lick White 1970 Baker 1994 Viznachennya intervalnoyi rozmirnosti grafa mozhna znajti v knizi Robertsa Anglijska nazva termina boxicity Roberts 1986 s 129 Scheinerman 1984 Brandstadt Le Spinrad 1999 s 54 Brandstadt Le Spinrad 1999 s 174 Syslo Proskurowski 1983 Kane Basu 1976 El Gindy 1985 Lin Skiena 1995 Brandstadt Le Spinrad 1999 Theorem 4 10 3 p 65 Wessel Poschel 1985 Unger 1988 LiteraturaF S Roberts Diskretnye matematicheskie modeli s prilozheniyami k socialnym biologicheskim i ekologicheskim zadacham Moskva Nauka 1986 S 129 Teoriya i metody sistemnogo analiza Brenda S Baker Approximation algorithms for NP complete problems on planar graphs 1994 T 41 vip 1 17 chervnya S 153 180 DOI 10 1145 174644 174650 Luis Boza Eugenio M Fedriani Juan Nunez The problem of outer embeddings in pseudosurfaces en 2004 T 71 17 chervnya S 79 91 Luis Boza Eugenio M Fedriani Juan Nunez Obstruction sets for outer bananas surface graphs en 2004 T 73 17 chervnya S 65 77 Luis Boza Eugenio M Fedriani Juan Nunez Uncountable graphs with all their vertices in one face 2006 T 112 4 17 chervnya S 307 313 DOI 10 1007 s10474 006 0082 0 Luis Boza Eugenio M Fedriani Juan Nunez Outer embeddability in certain pseudosurfaces arising from three spheres 2010 T 310 17 chervnya S 3359 3367 DOI 10 1016 j disc 2010 07 027 Andreas Brandstadt Van Bang Le Jeremy Spinrad Graph Classes A Survey Society for Industrial and Applied Mathematics 1999 SIAM Monographs on Discrete Mathematics and Applications ISBN 0 89871 432 X Gary Chartrand Frank Harary Planar permutation graphs Annales de l Institut Henri Poincare B 1967 T 3 vip 4 17 chervnya S 433 438 z dzherela 20 sichnya 2022 Procitovano 25 listopada 2020 Reinhard Diestel Graph Theory Springer Verlag 2000 T 173 S 107 ISBN 0 387 98976 5 H El Gindy Hierarchical decomposition of polygons with applications McGill University 1985 Ph D thesis Yak procitovano u Brandshtedta Li i Spinrada Brandstadt Le ta Spinrad 1999 Stefan Felsner Geometric graphs and arrangements some chapters from combinational geometry Vieweg Teubner Verlag 2004 S 6 ISBN 978 3 528 06972 8 Stanley Fiorini On the chromatic index of outerplanar graphs 1975 T 18 vip 1 17 chervnya S 35 38 Series B DOI 10 1016 0095 8956 75 90060 X Steve Fisk A short proof of Chvatal s watchman theorem 1978 T 24 17 chervnya S 374 Series B DOI 10 1016 0095 8956 78 90059 X Herbert J Fleischner D P Geller Frank Harary Outerplanar graphs and weak duals Journal of the Indian Mathematical Society 1974 T 38 17 chervnya S 215 219 Vinay G Kane Sanat K Basu On the depth of a planar graph 1976 T 14 vip 1 17 chervnya S 63 67 DOI 10 1016 0012 365X 76 90006 6 Ming Chu Li Derek G Corneil Eric Mendelsohn Pancyclicity and NP completeness in planar graphs 2000 T 98 vip 3 17 chervnya S 219 225 DOI 10 1016 S0166 218X 99 00163 8 Don R Lick Arthur T White k degenerate graphs 1970 T 22 17 chervnya S 1082 1096 DOI 10 4153 CJM 1970 125 1 z dzherela 23 lipnya 2012 Procitovano 25 listopada 2020 Yaw Ling Lin Steven S Skiena Complexity aspects of visibility graphs 1995 T 5 vip 3 17 chervnya S 289 312 DOI 10 1142 S0218195995000179 Andrzej Proskurowski Maciej M Syslo Efficient vertex and edge coloring of outerplanar graphs SIAM Journal on Algebraic and Discrete Methods 1986 T 7 17 chervnya S 131 136 DOI 10 1137 0607016 E R Scheinerman Intersection Classes and Multiple Intersection Parameters of a Graph Princeton University 1984 Ph D thesis As cited by Brandstadt Le ta Spinrad 1999 Maciej M Syslo Characterizations of outerplanar graphs 1979 T 26 vip 1 17 chervnya S 47 53 DOI 10 1016 0012 365X 79 90060 8 Maciej M Syslo Andrzej Proskurowski Graph Theory Proceedings of a Conference held in Lagow Poland February 10 13 1981 Springer Verlag 1983 T 1018 S 248 256 DOI 10 1007 BFb0071635 Walter Unger Proc 5th STACS 88 Springer Verlag 1988 T 294 S 61 72 DOI 10 1007 BFb0035832 W Wessel R Poschel Graphs Hypergraphs and Applications Proceedings of the Conference on Graph Theory Held in Eyba October 1st to 5th 1984 Horst Sachs B G Teubner 1985 T 73 S 207 210 Teubner Texte zur Mathematik Yak procituvav Unger Unger 1988 Posilannya Weisstein Eric W Zovniplanarnij graf angl na sajti Wolfram MathWorld

Дата публікації:
Топ