영역(그래프 도면)

Area (graph drawing)

그래프 도면에서 도면에 사용되는 영역은 도면의 품질을 측정하는 데 일반적으로 사용되는 방법이다.

정의

정점이 정수 격자에 배치되는 도면 스타일의 경우 도면의 면적은 도면의 가장 작은 축 정렬 경계 상자의 영역으로 정의될 수 있다. 즉, y 좌표의 차이가 가장 큰 두 정점의 x 좌표 차이가 가장 큰 제품이다.정점이 더 자유롭게 배치되는 다른 도면 스타일의 경우, 가장 가까운 정점 쌍이 서로 거리를 갖도록 도면을 축척할 수 있으며, 그 후에 면적을 도면의 최소 경계 상자의 영역으로 다시 정의할 수 있다.또는 적절한 스케일링 후 다시 도면의 볼록한 선체 영역으로 정의할 수 있다.[1]

다항식 한계

정점이 n인 평면 그래프의 직선 도면의 경우 도면의 영역에서 최적의 최악의 경우 경계는 θ(n2)이다.내포 삼각형 그래프는 어떻게 삽입되든 이만큼의 면적이 필요하며,[2] 대부분의 2차 영역에서 평면 그래프를 그릴 수 있는 몇 가지 방법이 알려져 있다.[3][4]이진수, 그리고 보다 일반적으로 경계가 있는 나무들은 그리기 스타일에 따라 선형 또는 거의 선형에 가까운 면적을 가진 도면을 가지고 있다.[5][6][7][8][9]모든 외측 평면 그래프는 정점 수에 면적 이차형인 직선 외측 평면도를 가지고 있다.[10][11] 만약 굴곡이나 교차가 허용된다면, 외측 평면 그래프에는 거의 선형에 가까운 면적을 가진 도면이 있다.[12][13]단, 도면 연속형-병렬 그래프는 가장자리를 폴리선으로 그릴 수 있더라도 n보다 큰 면적에 초폴리 로지스틱 계수를 곱해야 한다.[14]

지수 경계

이러한 다항식 한계와 대조적으로, 일부 도면 스타일은 면적이 기하급수적으로 증가할 수 있으며, 이는 이러한 스타일이 작은 그래프에만 적합할 수 있음을 암시한다.예를 들어, 최악의 경우 n-vertex 도면 면적이 2에n 비례할 수 있는 평면 방향의 평면 그래프를 위쪽으로 그리는 것이 그 예다.[15]평면 트리도 각 꼭지점 주위에 일정한 주기 순서를 유지하고 꼭지점 주위로 균일하게 간격을 두어야 하는 직선 가장자리로 그리려면 지수 영역이 필요할 수 있다.[16]

참조

  1. ^ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs (1st ed.), Prentice Hall, pp. 14–15, ISBN 0133016153.
  2. ^ Dolev, Danny; Leighton, Tom; Trickey, Howard (1984), "Planar embedding of planar graphs" (PDF), Advances in Computing Research, 2: 147–161
  3. ^ de Fraysseix, Hubert; Pach, János; Pollack, Richard (1988), "Small sets supporting Fary embeddings of planar graphs", Twentieth Annual ACM Symposium on Theory of Computing, pp. 426–433, doi:10.1145/62212.62254, ISBN 0-89791-264-0, S2CID 15230919.
  4. ^ Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148.
  5. ^ Crescenzi, P.; Di Battista, G.; Piperno, A. (1992), "A note on optimal area algorithms for upward drawings of binary trees", Computational Geometry Theory & Applications, 2 (4): 187–200, doi:10.1016/0925-7721(92)90021-J, MR 1196545.
  6. ^ Garg, Ashim; Goodrich, Michael T.; Tamassia, Roberto (1996), "Planar upward tree drawings with optimal area", International Journal of Computational Geometry & Applications, 6 (3): 333–356, doi:10.1142/S0218195996000228, MR 1409650.
  7. ^ Chan, T. M. (2002), "A near-linear area bound for drawing binary trees", Algorithmica, 34 (1): 1–13, doi:10.1007/s00453-002-0937-x, MR 1912924, S2CID 5122671.
  8. ^ Chan, Timothy M.; Goodrich, Michael T.; Kosaraju, S. Rao; Tamassia, Roberto (2002), "Optimizing area and aspect ratio in straight-line orthogonal tree drawings", Computational Geometry Theory & Applications, 23 (2): 153–162, doi:10.1016/S0925-7721(01)00066-9, MR 1922928.
  9. ^ Garg, Ashim; Rusu, Adrian (2004), "Straight-line drawings of binary trees with linear area and arbitrary aspect ratio", Journal of Graph Algorithms and Applications, 8 (2): 135–160, doi:10.7155/jgaa.00086, MR 2164808.
  10. ^ Garg, Ashim; Rusu, Adrian (2007), "Area-efficient planar straight-line drawings of outerplanar graphs", Discrete Applied Mathematics, 155 (9): 1116–1140, doi:10.1016/j.dam.2005.12.008, MR 2321019.
  11. ^ Di Battista, Giuseppe; Frati, Fabrizio (2009), "Small area drawings of outerplanar graphs", Algorithmica, 54 (1): 25–53, doi:10.1007/s00453-007-9117-3, MR 2496664, S2CID 2814656.
  12. ^ Biedl, Therese (2002), "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, Lecture Notes in Computer Science, vol. 2528, Springer, pp. 54–65, doi:10.1007/3-540-36151-0_6, MR 2063411.
  13. ^ Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Montecchiani, Fabrizio (2013), "Area requirement of graph drawings with few crossings per edge", Computational Geometry Theory & Applications, 46 (8): 909–916, doi:10.1016/j.comgeo.2013.03.001, MR 3061453.
  14. ^ Frati, Fabrizio (2011), "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, Lecture Notes in Computer Science, vol. 6502, pp. 220–225, doi:10.1007/978-3-642-18469-7_20, MR 2781267.
  15. ^ Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), "Area requirement and symmetry display of planar upward drawings", Discrete and Computational Geometry, 7 (4): 381–401, doi:10.1007/BF02187850, MR 1148953.
  16. ^ Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2013), "Drawing trees with perfect angular resolution and polynomial area", Discrete and Computational Geometry, 49 (2): 157–182, arXiv:1009.0581, doi:10.1007/s00454-012-9472-y, MR 3017904, S2CID 5000871.