Set universal de puncte
Probleme nerezolvate în matematică : este dimensiunea seturilor universale de puncte ale graficelor plane subpatratică?
O mulțime universală de puncte de ordin n este o mulțime S de puncte în planul euclidian cu proprietatea că orice graf plan cu n vârfuri are un model de muchii drepte în care toate vârfurile sunt situate în punctele din S .
Limite ale dimensiunilor setului universal de puncte
Dacă n este cel mult zece, există un set universal de puncte care are exact n puncte, dar pentru toate n ≥ sunt necesare 15 puncte suplimentare [1] .
Unii autori au arătat că o submulțime a unei rețele întregi de dimensiunea O ( n ) × O ( n ) este universală. În special, Freysix, Pach și Pollak [2] au arătat că rețeaua (2 n − 3) × ( n − 1) este universală, în timp ce Schneider [3] a redus rețeaua ( n − 1) × ( n − 1) la o submulţime triunghiulară ) cu n 2 /2 − O ( n ) puncte. Prin modificarea metodei lui Freysix, Pach și Schneider, Brandenburg [4] a găsit o încorporare a oricărui graf plan într-o submulțime triunghiulară a unei rețele care conține 4 n 2 /9 puncte. Un set universal de puncte sub forma unei rețele dreptunghiulare trebuie să aibă o dimensiune de cel puțin n /3 × n /3 [5] , dar acest lucru nu exclude posibilitatea existenței unui set universal mai mic de puncte de alte tipuri. . Cele mai mici seturi de puncte universale cunoscute nu se bazează pe rețele, ci sunt construite din superscheme ( permutări care conțin toate imaginile permutărilor de o dimensiune dată). Mulțimile de puncte universale construite în acest fel au dimensiunea n 2 /4 − O ( n ) [6] .
Freysix, Pach și Pollack [2] au demonstrat prima limită inferioară netrivială a mărimii unei mulțimi universale de puncte sub forma n + Ω(√ n ), în timp ce Chrobak și Karloff [7] au arătat că setul universal de puncte trebuie conțin cel puțin 1,098 n − o ( n ) puncte. Kurowski [8] a propus o limită și mai puternică 1.235 n − o ( n ), care rămâne cea mai bună limită inferioară [9] .
Închiderea decalajului dintre limitele liniare cunoscute și limitele superioare pătratice rămâne o problemă deschisă [10] .
Clase speciale de grafice
Subclasele de grafuri plane pot avea, în general, seturi universale mai mici (mulțimi de puncte care permit desenarea tuturor grafurilor cu n vârfuri cu muchii directe în subclasă) decât clasa completă a tuturor grafurilor plane și, în multe cazuri, există puncte universale. mulţimi care au precizie n puncte. De exemplu, este ușor de observat că orice set de n puncte în poziția convexă (care servesc ca vârfuri ale unui poligon convex) este universal pentru graficele planare exterioare cu n vârfuri și în special pentru arbori . Mai puțin evident, orice set de n puncte în poziție generală (nici trei nu se află pe aceeași linie) rămâne universal pentru graficele planare exterioare [11] .
Graficele plane care pot fi împărțite în bucle imbricate și graficele plane cu lățime de cale limitată au un set universal de puncte de dimensiune aproape liniară [12] [6] . Arborii planari 3 au seturi universale de puncte de dimensiunea O ( n 5/3 ). Aceeași limită este valabilă pentru graficele paralel-secvențiale [13] .
Alte stiluri de desen
Ca și în cazul desenului grafic cu margini drepte, seturile de puncte universale au fost studiate pentru alte stiluri. În cele mai multe dintre aceste cazuri, există seturi universale de puncte care au exact n puncte și se bazează pe o înglobare topologică de carte , în care vârfurile sunt situate pe o linie în plan, iar muchiile sunt desenate ca curbe care intersectează aceasta. linie cel mult o dată. De exemplu, orice set de n puncte coliniare este universală pentru o diagramă cu arc , în care fiecare muchie este reprezentată fie ca un singur semicerc , fie ca o curbă netedă formată din două semicercuri [14] .
Se poate demonstra că folosind un astfel de aranjament, orice curbă convexă din plan conține un subset de n puncte, care este universal pentru modelele de polilinii cu cel mult o întrerupere pe muchie [15] . Acest set conține doar vârfurile modelului, nu punctele de întrerupere. Se cunosc seturi mai mari care pot fi folosite pentru desene folosind linii întrerupte, în care vârfurile și toate punctele de întrerupere sunt puncte ale mulțimii [16] .
Note
- ↑ Cardinal, Hoffmann, Kusters, 2015 .
- ↑ 1 2 de Fraysseix, Pach și Pollack, 1988 .
- ↑ Schnyder, 1990 .
- ↑ Brandenburg, 2008 .
- ↑ Dolev, Leighton, Trickey, 1984 ; Chrobak și Karloff 1989 ; Demaine, O'Rourke, 2002–2012 . O limită pătratică mai slabă a dimensiunii rețelei necesară pentru desenele grafice plane a fost dată anterior de Valiant (1981 ).
- ↑ 1 2 Bannister, Cheng, Devanny, Eppstein, 2013 .
- ↑ Chrobak, Karloff, 1989 .
- ↑ Kurowski, 2004 .
- ↑ Mondal ( 2012 ) a susținut că dovada lui Kurowski a fost greșită, dar mai târziu (după o discuție cu Gene Cardinal) și-a retras afirmația. Vezi dovada lui Kurowski pentru o explicație Arhivată 15 martie 2017 la 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 .
Literatură
- 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. - T. 7034. - P. 75–85. — (LNCS). - doi : 10.1007/978-3-642-25878-7_8 .
- Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, David Eppstein. Proc. Al 21-lea Simpozion Internațional de Desen Grafic (HG 2013) . — 2013.
- Franz J. Brandenburg. Conferința internațională despre teoria graficelor topologice și geometrice. - Elsevier, 2008. - T. 31. - S. 37–40. — (Note electronice în matematică discretă). - 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. — (Note de curs în Informatică). - doi : 10.1007/978-3-540-24595-7_55 . . Vezi, în special, problema 11 de la pagina 520.
- Jean Cardinal, Michael Hoffmann, Vincent Kusters. Pe seturi universale de puncte pentru grafice plane // Journal of Graph Algorithms and Applications . - 2015. - T. 19 . — S. 529–547 . - doi : 10.7155/jgaa.00374 .
- M. Chrobak, H. Karloff. O limită inferioară a dimensiunii seturilor universale pentru graficele plane // SIGACT News . - 1989. - T. 20 . — p. 83–86 . - doi : 10.1145/74074.74088 .
- Hubert de Fraysseix, Janos Pach, Richard Pollack. Al XX-lea simpozion anual ACM privind teoria calculului . - 1988. - S. 426 -433. — ISBN 0-89791-264-0 . - doi : 10.1145/62212.62254 .
- E. Demaine, J. O'Rourke. Proiectul Probleme deschise. — 2002–2012.
- Danny Dolev, Tom Leighton, Howard Trickey. Încorporarea plană a graficelor plane // Progrese în cercetarea în calcul. - 1984. - T. 2 . — S. 147–161 .
- V. Dujmović, W.S. Evans, S. Lazard, W. Lenhart, G. Liotta, D. Rappaport, S.K. Wismath. Pe seturi de puncte care suportă grafice plane // Calcul. Geom. Teoria Apl .. - 2013. - T. 46 , nr. 1 . — S. 29–50 .
- Hazel Everett, Sylvain Lazard, Giuseppe Liotta, Stephen Wismath. Seturi universale de n puncte pentru desenele cu o singură curbură ale graficelor plane cu n vârfuri // Geometrie discretă și computațională . - 2010. - T. 43 , nr. 2 . — S. 272–288 . - doi : 10.1007/s00454-009-9149-3 .
- Radoslav Fulek, Csaba Toth. Simpozionul algoritmi și structuri de date (WADS) . — 2013.
- Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis. Algoritmi și calcul: 18th International Symposium, ISAAC 2007, Sendai, Japonia, 17-19 decembrie 2007, Proceedings. - Springer, 2007. - T. 4835. - S. 172-183. — (Note de curs în Informatică). - doi : 10.1007/978-3-540-77120-3_17 .
- P. Gritzmann, B. Mohar, Janos Pach, Richard Pollack. Încorporarea unei triangulații plane cu vârfuri în poziții specificate // American Mathematical Monthly . - 1991. - T. 98 , nr. 2 . — S. 165–166 .
- Maciej Kurowski. O limită inferioară de 1,235 a numărului de puncte necesare pentru a desena toate graficele plane n -vertex // Litere de procesare a informațiilor . - 2004. - T. 92 , nr. 2 . — S. 95–98 . - doi : 10.1016/j.ipl.2004.06.009 .
- Bojan Mohar. Deschideți Grădina cu probleme. — 2007.
- Debajyoti Mondal. Încorporarea unui grafic plan într-un set de puncte dat. - Departamentul de Informatică, Universitatea din Manitoba , 2012. - (Teză de master).
- Walter Schnyder. Proc. Primul Simpozion ACM/SIAM despre algoritmi discreti (SODA). - 1990. - S. 138-148.
- LG Valiant. Considerații de universalitate în circuitele VLSI // IEEE Transactions on Computers. - 1981. - T. C-30 , nr. 2 . — S. 135–140 . - doi : 10.1109/TC.1981.6312176 .