Площа (візуалізація графів)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Площа в задачах візуалізації графів — числова характеристика якості графічного подання графа.

Визначення характеристики залежить від вибраного стилю візуалізації. У техніці, в якій вершини розташовуються на цілочисельній ґратці, площу подання можна визначити як площу найменшого розташованого паралельно осям обмежувального прямокутника для подання, тобто як добуток найбільшої різниці координат двох вершин та найбільшої різниці координат двох вершин. Для інших стилів подання, в яких вершини розташовуються вільніше, подання можна звести до масштабу, за якого пара найближчих вершин має одиничну відстань, після чого площу подання можна визначити як найменший обмежувальний прямокутник малюнка. Альтернативно, площу можна визначити як площу опуклої оболонки подання, знову ж таки, за відповідного масштабу[1].

Поліноміальні межі

[ред. | ред. код]

Для намальованого з прямими ребрами планарного графа з вершинами оптимальною межею площі малюнка в гіршому випадку буде . Граф укладених трикутників вимагає такої площі незалежно від того, як він укладений[2], і відомі деякі методи, які дозволяють намалювати планарні графи з максимум квадратичною площею подання[3][4]. Двійкові дерева і дерева обмеженого степеня як загальніший випадок мають подання з лінійною або майже лінійною площею, що залежить від стилю малюнка[5][6][7][8][9]. Будь-який зовніпланарний граф має зовніпланарне подання з прямолінійними ребрами і субквадратичною від числа вершин площею[10][11], а якщо дозволено злами або схрещення, то зовніпланарні графи мають подання з майже лінійною площею[12][13]. Однак подання паралельно-послідовних графів вимагає площі, більшої від добутку на суперполілогарифмічну величину, навіть у разі дозволу малювати ребра у вигляді ламаних[14].

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

[ред. | ред. код]

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

Примітки

[ред. | ред. код]
  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. — ISBN 0133016153.
  • 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 ACM Symposium on Theory of Computing. — 1988. — С. 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. — С. 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 // Journal of Graph Algorithms and Applications. — 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 // Discrete and Computational Geometry. — 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 // Discrete and Computational Geometry. — 2013. — Т. 49, вип. 2. — С. 157–182. — arXiv:1009.0581. — DOI:10.1007/s00454-012-9472-y.
Отримано з https://uk.wikipedia.org/w/index.php?title=Площа_(візуалізація_графів)&oldid=36499308