Одночасне вкладення графів

Одноча́сне вкла́дення графів — це техніка візуалізації двох і більше різних графів на тій самій множині помічених вершин, за якої уникають схрещення ребер у кожному з графів. Схрещення між ребрами різних графів дозволяються, не дозволені тільки схрещення ребер одного графа[1].

Визначення

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

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

У задачах одночасного вкладення більше двох графів зазвичай вважається, що всі пари вхідних графів мають одні й самі схрещення. Тобто множини ребер і вершин утворюють соняшник[en] . Це обмеження відоме як перетин соняшника[1].

Одночасне геометричне вкладення

Багато результатів щодо одночасного геометричного вкладення ґрунтуються на ідеї, що декартові координати вершин двох заданих графів можна отримати із властивостей цих двох графів. Один з основних результатів такого типу — факт, що будь-які два шляхи на тій самій множині вершин завжди мають одночасне вкладення. Щоб знайти таке вкладення, можна використати позицію вершини у першому шляху як x-координати, а позицію вершини у другому шляху — як y-координати. У цьому випадку перший шлях буде намальований як x-монотонна ламана, яка автоматично не буде самоперетинатися, а другий шлях буде намальований як y-монотонна ламана[2].

Подібного роду малювання розміщує вершини на цілочисельній ґратці, розміри якої лінійно залежать від розміру графа. Схоже визначене розташування також працює, якщо обидва графи є гусеницями або обидва є циклами, хоча розміри ґратки будуть більшими, проте залишаються лінійно залежними від розмірів графа. Одночасне вкладення в ґратку, що лінійно залежить від розмірів графа, можливе для будь-якого числа графів, які є зірками. Інші пари графів, що дозволяють одночасне вкладення, але, можливо, що вимагають білших розмірів ґратки, це колесо і цикл, дерево і парування, а також пари графів, у яких найбільший степінь дорівнює двом. Однак існують пари планарного графа і парування або дерева і шляху, для яких одночасного (геометричного) вкладення не існує[3][4][5].

Перевірка, чи допускають два графи одночасне геометричне вкладення, є NP-складною задачею[1][6]. Точніше, вона NP-складна в екзистенційній теорії дійсних чисел. З доведень цього результату також випливає, що для деяких пар графів, що мають одночасне геометричне вкладення, найменша ґратка, на якій можна намалювати графи, має розмір, що залежить двічі експоненційно від розмірів графа[7][8].

Одночасне вкладення з фіксованими ребрами

Для одночасного вкладення з фіксованими ребрами класифікація різних видів вхідних графів, що завжди мають вкладення або іноді не мають вкладення, залежить не тільки від типів двох графів, що беруть участь, а також від структури їх перетину. Наприклад, коли обидва графи є зовніпланарними і їх перетин є лінійним лісом, завжди можна знайти таке вкладення, яке має не більше одного зламу на ребро з вершинами і точками зламу на ґратці з розміром, що поліноміально залежить від розміру графа. Існують, проте, інші пари зовніпланарних графів зі складнішими перетинами, які не мають такого вкладення. Можна також знайти одночасне вкладення з фіксованими ребрами для будь-якої пари планарного графа та дерева[9][10][11].

Нерозв'язана проблема математики:
Чи можна за поліноміальний час знайти для двох заданих графів одночасне вкладення з фіксованими ребрами?
(більше нерозв'язаних проблем математики)

Є відкритою проблема, чи можна перевірити існування одночасного вкладення з фіксованими ребрами за поліноміальний час. Однак для трьох і більше графів задача NP-складна. Одночасне вкладення з фіксованими ребрами можна знайти (якщо таке існує) за поліноміальний час для пари зовнішньопланових графів, а також для пари графів, перетин яких двозв'язний[1][12][13][14].

Необмежене одночасне вкладення

Будь-які два планарні графи мають одночасне вкладення. Це можна зробити на ґратці поліноміального розміру, ребра при цьому матимуть не більше двох зламів. Будь-які два підгамільтонові графи мають одночасне вкладення з максимум одним зламом на ребро[1][15].

Примітки

  1. ↑ а б в г д е ж Bläsius, Kobourov, Rutter, 2013, с. 349–383.
  2. ↑ Bläsius, Kobourov, Rutter, 2013, с. Theorem 11.1.
  3. ↑ Bläsius, Kobourov, Rutter, 2013, с. Figure 11.2.
  4. ↑ Brass, Cenek и др., 2007, с. 117–130.
  5. ↑ Cabello, van Kreveld и др., 2011, с. 79–96.
  6. ↑ Estrella-Balderrama, Gassner, Jünger, Percan, Schaefer, Schulz, 2008, с. 280–290.
  7. ↑ Cardinal, Kusters, 2015, с. 259–272.
  8. ↑ Duncan, Eppstein, Kobourov, 2004, с. 340–346.
  9. ↑ Bläsius, Kobourov, Rutter, 2013, с. Figure 11.5.
  10. ↑ Di Giacomo, Liotta, 2007, с. 139–160.
  11. ↑ Frati, 2007, с. 108–113.
  12. ↑ Fowler, Jünger, Kobourov, Schulz, 2011, с. 385–398.
  13. ↑ Gassner, Jünger, Percan, Schaefer, Schulz, 2006, с. 325–335.
  14. ↑ Haeupler, Jampani, Lubiw, 2013, с. 147–171.
  15. ↑ Di Giacomo, Liotta, 2005.

Література

Thomas Bläsius, Stephen G. Kobourov, Ignaz Rutter. Handbook of Graph Drawing and Visualization / Roberto Tamassia. — CRC Press, 2013. — ISBN 9781420010268.

  • Peter Brass, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, Joseph S. B. Mitchell. On simultaneous planar graph embeddings // Computational Geometry Theory & Applications. — 2007. — Т. 36, вип. 2. — С. 117–130. — DOI:10.1016/j.comgeo.2006.05.006.
  • Sergio Cabello, Marc van Kreveld, Giuseppe Liotta, Henk Meijer, Bettina Speckmann, Kevin Verbeek. Geometric simultaneous embeddings of a graph and a matching // Journal of Graph Algorithms and Applications. — 2011. — Т. 15, вип. 1. — С. 79–96. — DOI:10.7155/jgaa.00218.
  • Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz. Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers. — Berlin : Springer, 2008. — Т. 4875. — С. 280–290. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-77537-9_28.
  • Jean Cardinal, Vincent Kusters. The complexity of simultaneous geometric graph embedding // Journal of Graph Algorithms and Applications. — 2015. — Т. 19, вип. 1. — С. 259–272.
  • Christian Duncan, David Eppstein, Stephen G. Kobourov. Proc. 20th ACM Symposium on Computational Geometry. — ACM, 2004. — С. 340–346. — DOI:10.1145/997817.997868.
  • Emilio Di Giacomo, Giuseppe Liotta. Simultaneous embedding of outerplanar graphs, paths, and cycles // International Journal of Computational Geometry & Applications. — 2007. — Т. 17, вип. 2. — С. 139–160. — DOI:10.1142/S0218195907002276.
  • Fabrizio Frati. Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18–20, 2006, Revised Papers. — Berlin : Springer, 2007. — Т. 4372. — С. 108–113. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-70904-6_12.
  • J. Joseph Fowler, Michael Jünger, Stephen G. Kobourov, Michael Schulz. Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges // Computational Geometry Theory & Applications. — 2011. — Т. 44, вип. 8. — С. 385–398. — DOI:10.1016/j.comgeo.2011.02.002.
  • Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz. Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers. — Berlin : Springer, 2006. — Т. 4271. — С. 325–335. — (Lecture Notes in Computer Science) — DOI:10.1007/11917496_29.
  • Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw. Testing simultaneous planarity when the common graph is 2-connected // Journal of Graph Algorithms and Applications. — 2013. — Т. 17, вип. 3. — С. 147–171. — DOI:10.7155/jgaa.00289.
  • Emilio Di Giacomo, Giuseppe Liotta. 21st European Workshop on Computational Geometry. — Eindhoven University of Technology, 2005.

Read other articles:

Kim Seung-soo

Untuk produser musik, lihat Sweetune. Ini adalah nama Korea; marganya adalah Kim. Kim Seung-sooLahir25 Juli 1971 (umur 52)AlmamaterUniversitas Kyonggi - Bachelor of Physical Education[1]PekerjaanAktorTahun aktif1997-sekarangAgenPopeye Entertainment[1]Nama KoreaHangul김승수 Hanja金承洙 Alih AksaraGim SeungsuMcCune–ReischauerKim Sŭngsu Situs webhttp://kimseungsoo.com/ Kim Seung-Soo (lahir 25 Juli 1971[2]) adalah aktor asal Korea Selatan.[3] Fil...

 

 

Kuning malam

Kuning Malam Kaleng malamCommon connotationsLilin, malam     Koordinat warnaTriplet hex#F8E1A8sRGBB    (r, g, b)(248, 225, 168)CMYKH   (c, m, y, k)(0, 9, 32, 3)HSV       (h, s, v)(43°, 32%, 97%)SumberDaftar Istilah Warna[1]RAL Colours[2]B: Dinormalkan ke [0–255] (bita)H: Dinormalkan ke [0–100] (ratusan) Kuning malam (Inggris: Wax yellowcode: en is deprecated ) adalah suatu corak warna kuning pucat yang menyerupai warna lili...

 

 

Penaklukan Muslim Awal

Peta Penaklukan Awal Islam   Penaklukan sejak masa Muhammad, 622–632;   Penaklukan sejak masa Kekhalifahan Rasyidin, 632–661;   Penaklukan sejak masa Kekhalifahan Umayyah, 661–750 Penaklukan Muslim Arab (622–750), (bahasa Arab الغزوات, al-Ġazawāt atau bahasa Arab: الفتوحات الإسلامية, al-Futūḥāt al-Islāmiyya) (Arab: فتحcode: ar is deprecated , Fatah, berarti pembukaan,) juga disebut Penaklukan Islam atau Penaklukan Arab,&#...

Lakehead Thunderwolves

Lakehead ThunderwolvesUniversityLakehead UniversityAssociationU SportsConferenceOntario University AthleticsAthletic directorTom WardenLocationThunder Bay, OntarioArenaFort William GardensGymnasiumC.J. Sanders FieldhouseMascotWolfNicknameWolfieColoursBlue, White, and Yellow     Websitewww.thunderwolves.ca The Lakehead Thunderwolves are the U Sports varsity athletic teams that represent Lakehead University in Thunder Bay, Ontario, Canada. Sports activities Th...

 

 

Trièves

Trièves Le Trièves vu depuis le Jocou au sud-ouest en direction de la Mure et du massif du Taillefer. Massif Vercors / Diois / Dévoluy (Alpes) Pays France Région Auvergne-Rhône-Alpes Département Isère Coordonnées géographiques 44° 48′ nord, 5° 40′ est Géolocalisation sur la carte : France Trièves Géolocalisation sur la carte : Isère Trièves Orientation aval nord Longueur 30 km Type Écoulement Ébron Voie d'accès principale A51 - RD1075, lig...

 

 

George Yule (businessman)

Scottish merchant in England and India This article is about the British businessman and politician in India. For other persons of the same name, see George Yule (disambiguation). George Yule (17 April 1829 – 26 March 1892) was a Scottish merchant in England and India who served as the fourth President of the Indian National Congress in 1888 at Allahabad, the first non-Indian to hold that office.[1] He was founder of George Yule & Co. of London (now Synthomer, a FTSE 250 company...

Kapernaum

Kapernaumכפר נחוםGereja dibangun di atas rumah Petrus sesuai bentuk asli Gereja Bizantium yang dahulu berdiri di situ.Lokasi di Israel Timur LautLokasiIsraelKoordinat32°52′52″N 35°34′30″E / 32.88111°N 35.575°E / 32.88111; 35.575Catatan situsAkses umumyes Kapernaum (diucapkan k-pûrn-m; Ibrani כפר נחום Kefar Nahum, Kampung Nahum) adalah sebuah tempat tinggal di tepi Laut Galilea. Kini situs ini hanya tinggal reruntuhan saja, tetapi ditingg...

 

 

Luiz Vinhaes

Brazilian football manager (1896–1960) Luis Vinhaes Personal informationFull name Luis Augusto VinhaesDate of birth (1896-12-10)10 December 1896Place of birth Rio de Janeiro (RJ), BrazilDate of death 3 April 1960(1960-04-03) (aged 63)Place of death Rio de Janeiro (RJ), BrazilManagerial careerYears Team1926 São Cristóvão1929–1933 Fluminense[1]1931–1934 Brazil1933–1934 Bangu1949 Brazil U20[2] Luiz Augusto Vinhaes (10 December 1896 – 3 April 1960) was a Brazilia...

 

 

Jessica Giannino

American politician Jessica GianninoMember of the Massachusetts House of Representativesfrom the 16th Suffolk districtIncumbentAssumed office January 6, 2021Preceded byRoseLee Vincent Personal detailsBorn1991 (age 32–33)Political partyDemocraticEducationSalem State University (BA) Jessica Ann Giannino (born 1991) is a State representative for Revere in the Massachusetts House of Representatives.[1] She was elected to the Massachusetts house in 2020. She serv...

Contea di Surry (Virginia)

Questa voce sull'argomento contee della Virginia è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Contea di SurryconteaLocalizzazioneStato Stati Uniti Stato federato Virginia AmministrazioneCapoluogoSurry Data di istituzione1652 TerritorioCoordinatedel capoluogo37°07′00.88″N 76°53′17.92″W / 37.11691°N 76.88831°W37.11691; -76.88831 (Contea di Surry)Coordinate: 37°07′00.88″N 76°53′17.92″W / ࿯...

 

 

Філософія

Частина серії проФілософіяLeft to right: Plato, Kant, Nietzsche, Buddha, Confucius, AverroesПлатонКантНіцшеБуддаКонфуційАверроес Філософи Епістемологи Естетики Етики Логіки Метафізики Соціально-політичні філософи Традиції Аналітична Арістотелівська Африканська Близькосхідна іранська Буддій�...

 

 

Harukichi Hyakutake

Harukichi HyakutakeHarukichi Hyakutake di Rabaul, pada tahun 1942.Lahir25 May 1888Prefektur Saga, Jepang[1]Meninggal10 Maret 1947(1947-03-10) (umur 58)[2]Tokyo, JapanPengabdianKekaisaran JepangDinas/cabang Imperial Japanese ArmyLama dinas1909 – 1946[1]PangkatLetnan JenderalKomandan4th Mixed Brigade18th Infantry Division17th Army[1]Perang/pertempuranPerang Dunia II Perang Tiongkok-Jepang Kedua Kampanye militer Nugini Kampanye Guadalcanal Kampanye mil...

Lavrion Square–Strofyli railway

Lavrion Square–Strofyli railwayAttica Railways Locomotive Γ10OverviewNative nameΣιδηροδρομική Γραμμή Πλατείας Λαυρίου - ΣτροφυλίουStatusclosed (rebuilt as a rapid transit line)LocaleAttica, GreeceTerminiLavrion Square [el], AthensStrofyli [el], KifissiaStations23HistoryOpened4 February 1885 (1885-02-04)Closed8 August 1938 (1938-08-08)TechnicalLine length76 km (47 mi)Track gauge1,00...

 

 

1832 United States presidential election

12th quadrennial U.S. presidential election 1832 United States presidential election ← 1828 November 2 – December 5, 1832 1836 → 288 members of the Electoral College[a]145 electoral votes needed to winTurnout57.0%[1] 0.3 pp   Nominee Andrew Jackson Henry Clay Party Democratic National Republican Home state Tennessee Kentucky Running mate Martin Van Buren[b] John Sergeant Electoral vote 219 49 States carried 16 6 Popular&...

 

 

New China Life Insurance

New China Life Insurance Company Ltd.新华人寿保险股份有限公司 Тип Публичная компания Листинг на бирже SSE: 601336SEHK: 1336 Основание 1996 Расположение  Китай: Пекин Ключевые фигуры Лю Хаолин (председатель совета директоров)Ли Цюань (президент и CEO) Отрасль страхование (МСОК: 651) Продукция Страхов�...

语言瞭望站

此條目没有列出任何参考或来源。 (2015年8月4日)維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。 语言瞭望站（英語：Linguasphere Observatory，法語：Observatoire Linguistique，威爾斯語：Wylfa Ieithoedd）是一个跨国境的语言学网络研究计划。该计划于1983年在魁北克创建，随后以塞内加尔前总统利奥波德·塞达尔...

 

 

Barbie Dreams

Barbie Dreamssingolo discograficoScreenshot tratto dal video del branoArtistaNicki Minaj Pubblicazione14 agosto 2018 Durata4:39 Album di provenienzaQueen GenereHip hop EtichettaYoung Money, Cash Money, Republic Records ProduttoreMel and Mus, Ringo FormatiDownload digitale, streaming CertificazioniDischi d'argento Regno Unito[1](vendite: 200 000+) Dischi d'oro Australia[2](vendite: 35 000+) Brasile[3](vendite: 20 000+) Stati ...

 

 

شعار هولندا

شعار هولندا {{{alt}}}الشعار الحالي التفاصيل المستعمل هولندا البلد هولندا مملكة هولندا  الاعتماد 10 يوليو 190723 أبريل 1980 الدرع شعار نبالة لازوردي، مع أسد متوج بلون أصفر ومسلح، ذو لسان أحمر. في مخلبه الأيمن سيف فضي ومقبضه ذهبي اللون. وفي مخلبه الأيسر سبعة أسهم فضية اللون مدببة و�...

Gladstonian liberalism

British Victorian-era political doctrine Gladstone in 1879 This article is part of a series onLiberalismin the United Kingdom Schools Classical Gladstonian Libertarian Manchester Whiggist Conservative Muscular Economic Green Neo Radical Social Principles Capitalism Civil and political rights Due process Economic freedom Economic liberalism Environmentalism Equality before the law Freedom of the press Freedom of religion Freedom of speech Laissez-faire Natural law Rule of law Social justice We...

 

 

John Graham Haggart

Canadian politician For other people named John Haggart, see John Haggart (disambiguation). The HonourableJohn Graham HaggartMember of the Canadian Parliamentfor Lanark SouthIn office1872–1913Preceded byAlexander MorrisSucceeded byAdelbert Edward Hanna Personal detailsBorn(1836-11-14)November 14, 1836Perth, Upper CanadaDiedMarch 13, 1913(1913-03-13) (aged 76)Ottawa, Ontario, CanadaPolitical partyConservative John Graham Haggart, PC (November 14, 1836 – March 13, 1913) was a Canad...