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 вершинами оптимальною межею площі малюнка в гіршому випадку буде image. Граф укладених трикутників вимагає такої площі незалежно від того, як він укладений, і відомі деякі методи, які дозволяють намалювати планарні графи з максимум квадратичною площею подання. Двійкові дерева і дерева обмеженого степеня як загальніший випадок мають подання з лінійною або майже лінійною площею, що залежить від стилю малюнка. Будь-який зовніпланарний граф має зовніпланарне подання з прямолінійними ребрами і субквадратичною від числа вершин площею, а якщо дозволено або схрещення, то зовніпланарні графи мають подання з майже лінійною площею. Однак подання паралельно-послідовних графів вимагає площі, більшої від добутку image на суперполілогарифмічну величину, навіть у разі дозволу малювати ребра у вигляді ламаних.

Експоненціальні межі

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

Примітки

  1. Di Battista, Eades, Tamassia, Tollis, 1998, с. 14–15.
  2. Dolev, Leighton, Trickey, 1984, с. 147–161.
  3. de Fraysseix, Pach, Pollack, 1988, с. 426–433.
  4. Schnyder, 1990, с. 138–148.
  5. Crescenzi, Di Battista, Piperno, 1992, с. 187–200.
  6. Garg, Goodrich, Tamassia, 1996, с. 333–356.
  7. Chan, 2002, с. 1–13.
  8. Chan, Goodrich, Kosaraju, Tamassia, 2002, с. 153–162.
  9. Garg, Rusu, 2004, с. 135–160.
  10. Garg, Rusu, 2007, с. 1116–1140.
  11. Di Battista, Frati, 2009, с. 25–53.
  12. Biedl, 2002, с. 54–65.
  13. Di Giacomo, Didimo, Liotta, Montecchiani, 2013, с. 909–916.
  14. Frati, 2011, с. 220–225.
  15. Di Battista, Tamassia, Tollis, 1992, с. 381–401.
  16. Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2013, с. 157–182.

Література

  • Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1998. — С. 14–15. — .
  • Danny Dolev, F. Thomson Leighton, Howard Trickey. Planar embedding of planar graphs // Advances in Computing Research. — 1984. — Т. 2. — С. 147–161.
  • Hubert de Fraysseix, János Pach, Richard M. Pollack. Small sets supporting Fary embeddings of planar graphs // XX Annual . — 1988. — С. 426–433. — . — DOI:10.1145/62212.62254.
  • Walter Schnyder. Embedding planar graphs on the grid // Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
  • Crescenzi P., Di Battista G., Piperno A. A note on optimal area algorithms for upward drawings of binary trees // Computational Geometry Theory & Applications. — 1992. — Т. 2, вип. 4. — С. 187–200. — DOI:10.1016/0925-7721(92)90021-J.
  • Ashim Garg, Michael T. Goodrich, Roberto Tamassia. Planar upward tree drawings with optimal area // International Journal of Computational Geometry & Applications. — 1996. — Т. 6, вип. 3. — С. 333–356. — DOI:10.1142/S0218195996000228.
  • Timothy M. Chan. A near-linear area bound for drawing binary trees // Algorithmica. — 2002. — Т. 34, вип. 1. — С. 1–13. — DOI:10.1007/s00453-002-0937-x.
  • Timothy M. Chan, Michael T. Goodrich, S. Rao Kosaraju, Roberto Tamassia. Optimizing area and aspect ratio in straight-line orthogonal tree drawings // Computational Geometry Theory & Applications. — 2002. — Т. 23, вип. 2. — С. 153–162. — DOI:10.1016/S0925-7721(01)00066-9.
  • Ashim Garg, Adrian Rusu. Straight-line drawings of binary trees with linear area and arbitrary aspect ratio // . — 2004. — Т. 8, вип. 2. — С. 135–160. — DOI:10.7155/jgaa.00086.
  • Ashim Garg, Adrian Rusu. Area-efficient planar straight-line drawings of outerplanar graphs // Discrete Applied Mathematics. — 2007. — Т. 155, вип. 9. — С. 1116–1140. — DOI:10.1016/j.dam.2005.12.008.
  • Giuseppe Di Battista, Fabrizio Frati. Small area drawings of outerplanar graphs // Algorithmica. — 2009. — Т. 54, вип. 1. — С. 25–53. — DOI:10.1007/s00453-007-9117-3.
  • Therese Biedl. Drawing outer-planar graphs in O(n log n) area // Graph Drawing:10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers. — Springer, 2002. — Т. 2528. — С. 54–65. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-36151-0_6.
  • Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani. Area requirement of graph drawings with few crossings per edge // Computational Geometry Theory & Applications. — 2013. — Т. 46, вип. 8. — С. 909–916. — DOI:10.1016/j.comgeo.2013.03.001.
  • Fabrizio Frati. Improved lower bounds on the area requirements of series-parallel graphs // Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers. — 2011. — Т. 6502. — С. 220–225. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_20.
  • Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis. Area requirement and symmetry display of planar upward drawings // . — 1992. — Т. 7, вип. 4. — С. 381–401. — DOI:10.1007/BF02187850.
  • Christian A. Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Martin Nöllenburg. Drawing trees with perfect angular resolution and polynomial area // . — 2013. — Т. 49, вип. 2. — С. 157–182. — arXiv:1009.0581. — DOI:10.1007/s00454-012-9472-y.

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

Plosha v zadachah vizualizaciyi grafiv chislova harakteristika yakosti grafichnogo podannya grafa Viznachennya harakteristiki zalezhit vid vibranogo stilyu vizualizaciyi U tehnici v yakij vershini roztashovuyutsya na cilochiselnij gratci ploshu podannya mozhna viznachiti yak ploshu najmenshogo roztashovanogo paralelno osyam obmezhuvalnogo pryamokutnika dlya podannya tobto yak dobutok najbilshoyi riznici koordinat x displaystyle x dvoh vershin ta najbilshoyi riznici koordinat y displaystyle y dvoh vershin Dlya inshih stiliv podannya v yakih vershini roztashovuyutsya vilnishe podannya mozhna zvesti do masshtabu za yakogo para najblizhchih vershin maye odinichnu vidstan pislya chogo ploshu podannya mozhna viznachiti yak najmenshij obmezhuvalnij pryamokutnik malyunka Alternativno ploshu mozhna viznachiti yak ploshu opukloyi obolonki podannya znovu zh taki za vidpovidnogo masshtabu Polinomialni mezhiDlya namalovanogo z pryamimi rebrami planarnogo grafa z n displaystyle n vershinami optimalnoyu mezheyu ploshi malyunka v girshomu vipadku bude 8 n 2 displaystyle Theta n 2 Graf ukladenih trikutnikiv vimagaye takoyi ploshi nezalezhno vid togo yak vin ukladenij i vidomi deyaki metodi yaki dozvolyayut namalyuvati planarni grafi z maksimum kvadratichnoyu plosheyu podannya Dvijkovi dereva i dereva obmezhenogo stepenya yak zagalnishij vipadok mayut podannya z linijnoyu abo majzhe linijnoyu plosheyu sho zalezhit vid stilyu malyunka Bud yakij zovniplanarnij graf maye zovniplanarne podannya z pryamolinijnimi rebrami i subkvadratichnoyu vid chisla vershin plosheyu a yaksho dozvoleno abo shreshennya to zovniplanarni grafi mayut podannya z majzhe linijnoyu plosheyu Odnak podannya paralelno poslidovnih grafiv vimagaye ploshi bilshoyi vid dobutku n displaystyle n na superpolilogarifmichnu velichinu navit u razi dozvolu malyuvati rebra u viglyadi lamanih Eksponencialni mezhiDeyaki stili podannya mozhut pokazati eksponencialne zrostannya ploshi tak sho ci stili mozhut viyavitisya pridatnimi lishe dlya nevelikih grafiv Prikladom ye planarnih spryamovanih aciklichnih grafiv plosha yakih dlya podannya grafa z n displaystyle n vershinami u girshomu vipadku mozhe buti proporcijnoyu 2 n displaystyle 2 n Navit planarni dereva mozhut vimagati eksponencialnoyi ploshi yaksho voni namalovani pryamolinijnimi vidrizkami yaki zberigayut fiksovanij ciklichnij poryadok navkolo kozhnoyi vershini i mayut buti roztashovani z rivnimi vidstanyami vid vershini PrimitkiDi Battista Eades Tamassia Tollis 1998 s 14 15 Dolev Leighton Trickey 1984 s 147 161 de Fraysseix Pach Pollack 1988 s 426 433 Schnyder 1990 s 138 148 Crescenzi Di Battista Piperno 1992 s 187 200 Garg Goodrich Tamassia 1996 s 333 356 Chan 2002 s 1 13 Chan Goodrich Kosaraju Tamassia 2002 s 153 162 Garg Rusu 2004 s 135 160 Garg Rusu 2007 s 1116 1140 Di Battista Frati 2009 s 25 53 Biedl 2002 s 54 65 Di Giacomo Didimo Liotta Montecchiani 2013 s 909 916 Frati 2011 s 220 225 Di Battista Tamassia Tollis 1992 s 381 401 Duncan Eppstein Goodrich Kobourov Nollenburg 2013 s 157 182 LiteraturaGiuseppe Di Battista Peter Eades Roberto Tamassia Ioannis G Tollis Graph Drawing Algorithms for the Visualization of Graphs Prentice Hall 1998 S 14 15 ISBN 0133016153 Danny Dolev F Thomson Leighton Howard Trickey Planar embedding of planar graphs Advances in Computing Research 1984 T 2 S 147 161 Hubert de Fraysseix Janos Pach Richard M Pollack Small sets supporting Fary embeddings of planar graphs XX Annual 1988 S 426 433 ISBN 0 89791 264 0 DOI 10 1145 62212 62254 Walter Schnyder Embedding planar graphs on the grid Proc 1st ACM SIAM Symposium on Discrete Algorithms SODA 1990 S 138 148 Crescenzi P Di Battista G Piperno A A note on optimal area algorithms for upward drawings of binary trees Computational Geometry Theory amp Applications 1992 T 2 vip 4 S 187 200 DOI 10 1016 0925 7721 92 90021 J Ashim Garg Michael T Goodrich Roberto Tamassia Planar upward tree drawings with optimal area International Journal of Computational Geometry amp Applications 1996 T 6 vip 3 S 333 356 DOI 10 1142 S0218195996000228 Timothy M Chan A near linear area bound for drawing binary trees Algorithmica 2002 T 34 vip 1 S 1 13 DOI 10 1007 s00453 002 0937 x Timothy M Chan Michael T Goodrich S Rao Kosaraju Roberto Tamassia Optimizing area and aspect ratio in straight line orthogonal tree drawings Computational Geometry Theory amp Applications 2002 T 23 vip 2 S 153 162 DOI 10 1016 S0925 7721 01 00066 9 Ashim Garg Adrian Rusu Straight line drawings of binary trees with linear area and arbitrary aspect ratio 2004 T 8 vip 2 S 135 160 DOI 10 7155 jgaa 00086 Ashim Garg Adrian Rusu Area efficient planar straight line drawings of outerplanar graphs Discrete Applied Mathematics 2007 T 155 vip 9 S 1116 1140 DOI 10 1016 j dam 2005 12 008 Giuseppe Di Battista Fabrizio Frati Small area drawings of outerplanar graphs Algorithmica 2009 T 54 vip 1 S 25 53 DOI 10 1007 s00453 007 9117 3 Therese Biedl Drawing outer planar graphs in O n log n area Graph Drawing 10th International Symposium GD 2002 Irvine CA USA August 26 28 2002 Revised Papers Springer 2002 T 2528 S 54 65 Lecture Notes in Computer Science DOI 10 1007 3 540 36151 0 6 Emilio Di Giacomo Walter Didimo Giuseppe Liotta Fabrizio Montecchiani Area requirement of graph drawings with few crossings per edge Computational Geometry Theory amp Applications 2013 T 46 vip 8 S 909 916 DOI 10 1016 j comgeo 2013 03 001 Fabrizio Frati Improved lower bounds on the area requirements of series parallel graphs Graph Drawing 18th International Symposium GD 2010 Konstanz Germany September 21 24 2010 Revised Selected Papers 2011 T 6502 S 220 225 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 20 Giuseppe Di Battista Roberto Tamassia Ioannis G Tollis Area requirement and symmetry display of planar upward drawings 1992 T 7 vip 4 S 381 401 DOI 10 1007 BF02187850 Christian A Duncan David Eppstein Michael T Goodrich Stephen G Kobourov Martin Nollenburg Drawing trees with perfect angular resolution and polynomial area 2013 T 49 vip 2 S 157 182 arXiv 1009 0581 DOI 10 1007 s00454 012 9472 y

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