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

Нерозв язана проблема математики Розмір універсальних множин точок планарних графів підквадратичний Універсальна множина

Універсальна множина точок

Універсальна множина точок

Розмір універсальних множин точок планарних графів підквадратичний?

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

Межі розмірів універсальної множини точок

image
Малюнок графа вкладених трикутників на ґратці. У будь-якому малюнку цього графа принаймні половина трикутників повинна утворювати вкладений ланцюжок, так що знадобиться обмежувальний прямокутник розміром щонайменше n/3 × n/3. Наведене на малюнку подання графа має близьке до цього значення n/3 × n/2

Якщо n не перевищує 10, існує універсальна множина точок, що має рівно n точок, але для всіх n ≥ 15 знадобляться додаткові точки.

Деякі автори показали, що підмножина цілої ґратки розміру O(n) × O(n) є універсальною. Зокрема, Фрейсікс, Пах і Поллак показали, що ґратка (2n − 3) × (n − 1) є універсальною, а Шнайдер зменшив до трикутної підмножини ґратки (n − 1) × (n − 1) з n2/2 − O(n) точками. Модифікуючи метод Фрейсікса, Паха і Шнайдера, Бранденбург знайшов вкладення будь-якого планарного графа в трикутну підмножину ґратки, що містить 4n2/9 точок. Універсальна множина точок у вигляді прямокутної ґратки повинна мати розмір щонайменше n/3 × n/3, але це виключає можливість існування меншої універсальної множини точок інших типів. Найменші відомі універсальні множини точок не засновані на ґратках, а будуються зі [en] (перестановок, що містять усі [en] заданого розміру). Універсальні множини точок, побудовані так, мають розмір n2/4 − O(n).

Фрейсікс, Пах і Поллак довели першу нетривіальну нижню межу розміру універсальної множини точок у вигляді n + Ω(√n), а Кробак і Карлофф показали, що універсальна множина точок має містити щонайменше 1.098n − o(n) точок. Куровскі запропонував навіть сильнішу межу 1.235n − o(n), яка залишається кращою нижньою межею.

Закриття проміжку між відомими лінійними межами та квадратичними верхніми межами залишається відкритою проблемою.

Спеціальні класи графів

Підкласи планарних графів можуть, у загальному випадку, мати менші універсальні множини (множини точок, які дозволяють малювання всіх графів підкласу з n вершинами з прямими ребрами), ніж повний клас усіх планарних графів, і в багатьох випадках існують універсальні множини точок, що мають рівно n точок. Наприклад, нескладно бачити, що будь-яка множина з n точок у [en] (які служать вершинами опуклого многокутника), є універсальною для n вершинних зовніпланарних графів, і, зокрема, для дерев. Менш очевидно, що будь-яка множина з n точок у загальному положенні (ніякі три не лежать на одній прямій) залишається універсальною для зовніпланарних графів.

Планарні графи, які можна розбити на вкладені цикли, та планарні графи з обмеженою шляховою шириною мають універсальну множину точок майже лінійного розміру. Планарні 3-дерева мають універсальні множини точок розміру O(n5/3). Та сама межа існує для паралельно-послідовних графів.

Інші способи малювання

image
Дугова діаграма

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

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

Примітки

  1. Cardinal, Hoffmann, Kusters, 2015.
  2. de Fraysseix, Pach, Pollack, 1988.
  3. Schnyder, 1990.
  4. Brandenburg, 2008.
  5. Dolev, Leighton, Trickey, 1984; Chrobak, Karloff, 1989; Demaine, O'Rourke, 2002–2012. Слабшу квадратичну межу на розмір ґратки, потрібної для малювання планарного графа, дав до цього Валіант Valiant, (1981).
  6. Bannister, Cheng, Devanny, Eppstein, 2013.
  7. Chrobak, Karloff, 1989.
  8. Kurowski, 2004.
  9. Мондал (Mondal, 2012) стверджував, що доведення Куровскі хибне, але пізніше (після обговорення з Джином Кардіналом) відкликав своє твердження. Див. Пояснення доведення Куровскі [ 2017-03-15 у Wayback Machine.].
  10. Demaine, O'Rourke, 2002–2012; Brandenburg, Eppstein, Goodrich, Kobourov, 2003; Mohar, 2007.
  11. Gritzmann, Mohar, Pach, Pollack, 1991.
  12. Angelini, Di Battista, Kaufmann, Mchedlidze, 2012.
  13. Fulek, Toth, 2013.
  14. Giordano, Liotta, Mchedlidze, Symvonis, 2007.
  15. Everett, Lazard, Liotta, Wismath, 2010.
  16. Dujmović, Evans, Lazard, Lenhart, 2013.

Література

  • Patrizio Angelini, Giuseppe Di Battista, Michael Kaufmann, Tamara Mchedlidze, Vincenzo Roselli, Claudio Squarcella. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21–23, 2011, Revised Selected Papers / Marc van Kreveld, Bettina Speckmann. — Berlin, Heidelberg : Springer-Verlag, 2012. — Т. 7034. — С. 75–85. — (LNCS) — DOI:10.1007/978-3-642-25878-7_8.
  • Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, David Eppstein. Proc. 21st International Symposium on Graph Drawing (GD 2013). — 2013.
  • Franz J. Brandenburg. The International Conference on Topological and Geometric Graph Theory. — Elsevier, 2008. — Т. 31. — С. 37–40. — (Electronic Notes in Discrete Mathematics) — DOI:10.1016/j.endm.2008.06.005.
  • Franz-Josef Brandenburg, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Giuseppe Liotta, Petra Mutzel. Graph Drawing: 11th International Symposium, GD 2003, Perugia, Italy, September 21–24, 2003 Revised Papers / Giuseppe Liotta. — Springer-Verlag, 2003. — Т. 2912. — С. 515–539. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-24595-7_55.. Див., зокрема, задачу 11 на стор. 520.
  • Jean Cardinal, Michael Hoffmann, Vincent Kusters. On universal point sets for planar graphs // . — 2015. — Т. 19. — С. 529–547. — DOI:10.7155/jgaa.00374.
  • M. Chrobak, H. Karloff. A lower bound on the size of universal sets for planar graphs // . — 1989. — Т. 20. — С. 83–86. — DOI:10.1145/74074.74088.
  • Hubert de Fraysseix, János Pach, Richard Pollack. . — 1988. — С. 426–433. — . — DOI:10.1145/62212.62254.
  • E. Demaine, J. O'Rourke. The Open Problems Project. — 2002–2012.
  • Danny Dolev, Tom Leighton, Howard Trickey. Planar embedding of planar graphs // Advances in Computing Research. — 1984. — Т. 2. — С. 147–161.
  • V. Dujmović, W. S. Evans, S. Lazard, W. Lenhart, G. Liotta, D. Rappaport, S. K. Wismath. On point-sets that support planar graphs // Comput. Geom. Theory Appl.. — 2013. — Т. 46, вип. 1. — С. 29–50.
  • Hazel Everett, Sylvain Lazard, Giuseppe Liotta, Stephen Wismath. Universal Sets of n Points for One-Bend Drawings of Planar Graphs with n Vertices // . — 2010. — Т. 43, вип. 2. — С. 272–288. — DOI:10.1007/s00454-009-9149-3.
  • Radoslav Fulek, Csaba Toth. . — 2013.
  • Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings. — Springer, 2007. — Т. 4835. — С. 172–183. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-77120-3_17.
  • P. Gritzmann, B. Mohar, János Pach, Richard Pollack. Embedding a planar triangulation with vertices at specified positions // American Mathematical Monthly. — 1991. — Т. 98, вип. 2. — С. 165–166.
  • Maciej Kurowski. A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs // . — 2004. — Т. 92, вип. 2. — С. 95–98. — DOI:10.1016/j.ipl.2004.06.009.
  • Bojan Mohar. Open Problem Garden. — 2007.
  • Debajyoti Mondal. Embedding a Planar Graph on a Given Point Set. — Department of Computer Science, University of Manitoba, 2012. — (Masters thesis)
  • Walter Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
  • L. G. Valiant. Universality considerations in VLSI circuits // IEEE Transactions on Computers. — 1981. — Т. C-30, вип. 2. — С. 135–140. — DOI:10.1109/TC.1981.6312176.

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

Nerozv yazana problema matematiki Rozmir universalnih mnozhin tochok planarnih grafiv pidkvadratichnij Universalna mnozhina tochok poryadku n ce mnozhina S tochok evklidovoyi ploshini z vlastivistyu sho bud yakij planarnij graf z n vershinami maye malyunok iz pryamimi rebrami v yakomu vsi vershini roztashovuyutsya v tochkah mnozhini S Mezhi rozmiriv universalnoyi mnozhini tochokMalyunok grafa vkladenih trikutnikiv na gratci U bud yakomu malyunku cogo grafa prinajmni polovina trikutnikiv povinna utvoryuvati vkladenij lancyuzhok tak sho znadobitsya obmezhuvalnij pryamokutnik rozmirom shonajmenshe n 3 n 3 Navedene na malyunku podannya grafa maye blizke do cogo znachennya n 3 n 2 Yaksho n ne perevishuye 10 isnuye universalna mnozhina tochok sho maye rivno n tochok ale dlya vsih n 15 znadoblyatsya dodatkovi tochki Deyaki avtori pokazali sho pidmnozhina ciloyi gratki rozmiru O n O n ye universalnoyu Zokrema Frejsiks Pah i Pollak pokazali sho gratka 2n 3 n 1 ye universalnoyu a Shnajder zmenshiv do trikutnoyi pidmnozhini gratki n 1 n 1 z n2 2 O n tochkami Modifikuyuchi metod Frejsiksa Paha i Shnajdera Brandenburg znajshov vkladennya bud yakogo planarnogo grafa v trikutnu pidmnozhinu gratki sho mistit 4n2 9 tochok Universalna mnozhina tochok u viglyadi pryamokutnoyi gratki povinna mati rozmir shonajmenshe n 3 n 3 ale ce viklyuchaye mozhlivist isnuvannya menshoyi universalnoyi mnozhini tochok inshih tipiv Najmenshi vidomi universalni mnozhini tochok ne zasnovani na gratkah a buduyutsya zi en perestanovok sho mistyat usi en zadanogo rozmiru Universalni mnozhini tochok pobudovani tak mayut rozmir n2 4 O n Frejsiks Pah i Pollak doveli pershu netrivialnu nizhnyu mezhu rozmiru universalnoyi mnozhini tochok u viglyadi n W n a Krobak i Karloff pokazali sho universalna mnozhina tochok maye mistiti shonajmenshe 1 098n o n tochok Kurovski zaproponuvav navit silnishu mezhu 1 235n o n yaka zalishayetsya krashoyu nizhnoyu mezheyu Zakrittya promizhku mizh vidomimi linijnimi mezhami ta kvadratichnimi verhnimi mezhami zalishayetsya vidkritoyu problemoyu Specialni klasi grafivPidklasi planarnih grafiv mozhut u zagalnomu vipadku mati menshi universalni mnozhini mnozhini tochok yaki dozvolyayut malyuvannya vsih grafiv pidklasu z n vershinami z pryamimi rebrami nizh povnij klas usih planarnih grafiv i v bagatoh vipadkah isnuyut universalni mnozhini tochok sho mayut rivno n tochok Napriklad neskladno bachiti sho bud yaka mnozhina z n tochok u en yaki sluzhat vershinami opuklogo mnogokutnika ye universalnoyu dlya n vershinnih zovniplanarnih grafiv i zokrema dlya derev Mensh ochevidno sho bud yaka mnozhina z n tochok u zagalnomu polozhenni niyaki tri ne lezhat na odnij pryamij zalishayetsya universalnoyu dlya zovniplanarnih grafiv Planarni grafi yaki mozhna rozbiti na vkladeni cikli ta planarni grafi z obmezhenoyu shlyahovoyu shirinoyu mayut universalnu mnozhinu tochok majzhe linijnogo rozmiru Planarni 3 dereva mayut universalni mnozhini tochok rozmiru O n5 3 Ta sama mezha isnuye dlya paralelno poslidovnih grafiv Inshi sposobi malyuvannyaDugova diagrama Yak i v razi malyuvannya grafiv iz pryamimi rebrami universalni mnozhini tochok vivchalisya dlya inshih sposobiv malyuvannya U bilshosti vipadkiv isnuyut universalni mnozhini tochok sho mayut rivno n tochok i gruntuyutsya voni na topologichnomu knizhkovomu vkladenni v yakomu vershini roztashovuyutsya na pryamij na ploshini a rebra malyuyutsya yak krivi yaki peretinayut cyu liniyu maksimum odin raz Napriklad bud yaka mnozhina n kolinearnih tochok ye universalnoyu dlya dugovoyi diagrami v yakij kozhne rebro podano abo yak odne pivkolo abo yak gladka kriva utvorena dvoma pivkolami Mozhna pokazati sho za vikoristannya podibnogo roztashuvannya bud yaka opukla kriva na ploshini mistit pidmnozhinu z n tochok sho ye universalnoyu dlya malyunkiv u viglyadi lamanih iz maksimum odnim zlamom na rebro Cya mnozhina mistit tilki vershini malyunka ale ne tochki zlamu Vidomi veliki mnozhini yaki mozhna vikoristovuvati dlya malyunkiv za dopomogoyu lamanih u yakih vershini i vsi tochki zlamu ye tochkami mnozhini PrimitkiCardinal Hoffmann Kusters 2015 de Fraysseix Pach Pollack 1988 Schnyder 1990 Brandenburg 2008 Dolev Leighton Trickey 1984 Chrobak Karloff 1989 Demaine O Rourke 2002 2012 Slabshu kvadratichnu mezhu na rozmir gratki potribnoyi dlya malyuvannya planarnogo grafa dav do cogo Valiant Valiant 1981 Bannister Cheng Devanny Eppstein 2013 Chrobak Karloff 1989 Kurowski 2004 Mondal Mondal 2012 stverdzhuvav sho dovedennya Kurovski hibne ale piznishe pislya obgovorennya z Dzhinom Kardinalom vidklikav svoye tverdzhennya Div Poyasnennya dovedennya Kurovski 2017 03 15 u Wayback Machine Demaine O Rourke 2002 2012 Brandenburg Eppstein Goodrich Kobourov 2003 Mohar 2007 Gritzmann Mohar Pach Pollack 1991 Angelini Di Battista Kaufmann Mchedlidze 2012 Fulek Toth 2013 Giordano Liotta Mchedlidze Symvonis 2007 Everett Lazard Liotta Wismath 2010 Dujmovic Evans Lazard Lenhart 2013 LiteraturaPatrizio Angelini Giuseppe Di Battista Michael Kaufmann Tamara Mchedlidze Vincenzo Roselli Claudio Squarcella Graph Drawing 19th International Symposium GD 2011 Eindhoven The Netherlands September 21 23 2011 Revised Selected Papers Marc van Kreveld Bettina Speckmann Berlin Heidelberg Springer Verlag 2012 T 7034 S 75 85 LNCS DOI 10 1007 978 3 642 25878 7 8 Michael J Bannister Zhanpeng Cheng William E Devanny David Eppstein Proc 21st International Symposium on Graph Drawing GD 2013 2013 Franz J Brandenburg The International Conference on Topological and Geometric Graph Theory Elsevier 2008 T 31 S 37 40 Electronic Notes in Discrete Mathematics DOI 10 1016 j endm 2008 06 005 Franz Josef Brandenburg David Eppstein Michael T Goodrich Stephen G Kobourov Giuseppe Liotta Petra Mutzel Graph Drawing 11th International Symposium GD 2003 Perugia Italy September 21 24 2003 Revised Papers Giuseppe Liotta Springer Verlag 2003 T 2912 S 515 539 Lecture Notes in Computer Science DOI 10 1007 978 3 540 24595 7 55 Div zokrema zadachu 11 na stor 520 Jean Cardinal Michael Hoffmann Vincent Kusters On universal point sets for planar graphs 2015 T 19 S 529 547 DOI 10 7155 jgaa 00374 M Chrobak H Karloff A lower bound on the size of universal sets for planar graphs 1989 T 20 S 83 86 DOI 10 1145 74074 74088 Hubert de Fraysseix Janos Pach Richard Pollack 1988 S 426 433 ISBN 0 89791 264 0 DOI 10 1145 62212 62254 E Demaine J O Rourke The Open Problems Project 2002 2012 Danny Dolev Tom Leighton Howard Trickey Planar embedding of planar graphs Advances in Computing Research 1984 T 2 S 147 161 V Dujmovic W S Evans S Lazard W Lenhart G Liotta D Rappaport S K Wismath On point sets that support planar graphs Comput Geom Theory Appl 2013 T 46 vip 1 S 29 50 Hazel Everett Sylvain Lazard Giuseppe Liotta Stephen Wismath Universal Sets of n Points for One Bend Drawings of Planar Graphs with n Vertices 2010 T 43 vip 2 S 272 288 DOI 10 1007 s00454 009 9149 3 Radoslav Fulek Csaba Toth 2013 Francesco Giordano Giuseppe Liotta Tamara Mchedlidze Antonios Symvonis Algorithms and Computation 18th International Symposium ISAAC 2007 Sendai Japan December 17 19 2007 Proceedings Springer 2007 T 4835 S 172 183 Lecture Notes in Computer Science DOI 10 1007 978 3 540 77120 3 17 P Gritzmann B Mohar Janos Pach Richard Pollack Embedding a planar triangulation with vertices at specified positions American Mathematical Monthly 1991 T 98 vip 2 S 165 166 Maciej Kurowski A 1 235 lower bound on the number of points needed to draw all n vertex planar graphs 2004 T 92 vip 2 S 95 98 DOI 10 1016 j ipl 2004 06 009 Bojan Mohar Open Problem Garden 2007 Debajyoti Mondal Embedding a Planar Graph on a Given Point Set Department of Computer Science University of Manitoba 2012 Masters thesis Walter Schnyder Proc 1st ACM SIAM Symposium on Discrete Algorithms SODA 1990 S 138 148 L G Valiant Universality considerations in VLSI circuits IEEE Transactions on Computers 1981 T C 30 vip 2 S 135 140 DOI 10 1109 TC 1981 6312176

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