원형 레이아웃
Circular layout
그래프 그리기에서 원형 레이아웃은 그래프의 정점을 원에 배치하는 그리기 스타일이며, 보통 일반 폴리곤의 정점을 형성하도록 균일한 간격을 둡니다.
적용들
원형 레이아웃은 스타 또는 링 네트워크 [1]등의 통신 네트워크 토폴로지 및 대사 네트워크의 [2]순환 부분에 적합합니다.알려진 해밀턴 주기가 있는 그래프의 경우 원형 레이아웃은 순환을 원으로 묘사할 수 있으며, 이러한 방식으로 원형 레이아웃은 해밀턴 입방 [3]그래프에 대한 LCF 표기법의 기초를 형성합니다.
원형 레이아웃은 전체 그래프 도면에 대해 단독으로 사용될 수 있지만, 그 쌍커넥티드 성분,[4] 유전자 상호작용 [5]그래프 내의 유전자 클러스터 또는 소셜 네트워크 [6]내의 자연 서브그룹과 같은 더 큰 그래프 도면 내의 정점들의 작은 클러스터를 위한 레이아웃으로도 사용될 수 있다.이러한 방법으로 여러 정점 원을 사용하는 경우 강제 방향 그래프 그리기 등의 다른 방법을 사용하여 클러스터를 [7]정렬할 수 있습니다.
둥근 레이아웃의 일부 응용, 생물 정보학 또는 사회적 네트워크 시각화 등의 한 장점은 그것의 중립성:서로에게 그리고 그림의 중심에서 등거리에 모든 vertices을 배치하여[8], 아무도 시청자들의 경향은 중앙에 위치한 노드들을 인지하기에 대응하고 자신이 상당히 축복 받은 위치 주어진다.가 어떻게 되더 [9]중요하기 때문입니다.
엣지
도면의 가장자리는 원의 [10]화음, 원형[11] 호(아마도 정점 원에 수직이며 쌍곡기하학의 Poincaré 디스크 모델의 모서리 모델 선) 또는 다른 유형의 [12]곡선으로 표시될 수 있습니다.
원형 레이아웃에서 정점 원의 안쪽과 바깥쪽 사이의 시각적 구별을 사용하여 두 가지 다른 스타일의 모서리 도면을 구분할 수 있습니다.예를 들어 Gansner & Koren(2007)의 원형 그리기 알고리즘은 원 안에 [12]엣지 번들링과 함께 원 밖에 그려지는 번들링되지 않은 일부 엣지를 사용한다.
모서리가 원형 호로 그려진 일반 그래프의 원형 레이아웃의 경우,[11] 도면의 각도 분해능 최적화를 단순화하는 특성인 정점 원을 가진 이러한 호 중 하나의 입사 각도가 호 양 끝에서 동일합니다.
건널목수
여러 저자들은 모든 모서리가 정점 원 안에 그려질 때 모서리 교차 수를 최소화하는 원형 레이아웃의 정점 순열을 찾는 문제를 연구했다.이 교차 [13]횟수는 외부 평면 그래프에 대해서만 0입니다.다른 그래프의 경우, 이러한 성분이 상호 [14]작용하지 않도록 그려질 수 있으므로 솔루션을 결합하기 전에 그래프의 각 쌍접합 구성요소에 대해 개별적으로 최적화되거나 축소될 수 있다.
일반적으로 교차수를 최소화하는 것은 [15]NP-완전이지만 O(log2 n)의 근사비로 근사할 수 있다.여기서 n은 [16]정점수이다.교차 복잡성을 줄이기 위한 휴리스틱 방법도 예를 들어 신중한 정점 삽입 순서와 국소 [17]최적화를 기반으로 고안되었다.
원형 레이아웃을 사용하여 교차 횟수를 최대화할 수도 있습니다.특히 정점에 대한 랜덤 순열을 선택하면 가능한 각 교차가 1/3 확률로 발생하므로 예상 교차 수는 가능한 모든 레이아웃 중 최대 교차 수 중 3배 이내입니다.이 방법을 역andomizing하면 근사비 [18]3을 갖는 결정론적 근사 알고리즘을 얻을 수 있다.
기타 최적화 기준
교차와 함께 원형 레이아웃의 가장자리 길이 최적화 문제, 교차의 각도 분해능 또는 절단 폭(원호 1개와 반대쪽 호를 연결하는 최대 가장자리 수)에 대한 원형 버전도 [19]고려되었지만 이러한 문제의 대부분은 NP-완전입니다.[20]
「 」를 참조해 주세요.
- 정보 시각화에서 밀접하게 관련된 개념인 코드 다이어그램(정보 시각화)
- 플레이어가 평면 그래프의 그림을 풀기 위해 정점을 이동해야 하는 퍼즐인 Planarity(평면성)로, 무작위 원형 레이아웃에서 시작합니다.
메모들
- ^ Dozrusöz, Madden & Madden(1997).
- ^ Becker & Rojas (2001년).
- ^ Pisanski & Servatius (2013).
- ^ Dorusrusöz, Madden & Madden(1997), Six & Tollis(1999b).
- ^ Symonidis & Tollis (2004년).
- ^ 크렙스(1996년).
- ^ Dorusrusöz, Belviranli & Delek(2012).
- ^ 이라뉴 등 (2005년).
- ^ Huang, Hong & Eades(2007).
- ^ Six & Tollis(1999a).
- ^ a b 던컨 외 연구진(2012).
- ^ a b Gansner & Koren (2007).
- ^ Six & Tollis(1999a), Baur & Brandes(2005).
- ^ Baur & Brandes (2005년).
- ^ 마스다 외(1987년)
- ^ 샤로키 외 연구진(1995년)
- ^ Mékinen(1988년); Doörusöz, Madden & Madden(1997년); Six & Tollis(1999a);He & S skora (2004년), Baur & Brandes (2005년).
- ^ Verbitsky (2008).
- ^ Makinen(1988년), Gansner & Koren(2007년);Nguyen et al. (2011);Dehkordi 등 (2013년)
- ^ 매키넨(1988년).
레퍼런스
- 를 클릭합니다Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, doi:10.1007/978-3-540-30559-0_28.
- 를 클릭합니다Becker, Moritz Y.; Rojas, Isabel (2001), "A graph layout algorithm for drawing metabolic pathways", Bioinformatics, 17 (5): 461–467, doi:10.1093/bioinformatics/17.5.461, PMID 11331241.
- Dehkordi, Hooman Reisi, 응우옌, 권;Eades, 피터,, Seok-Hee(2013년)," 큰 크로싱의 각도를 원형으로 된 그래프 그림", 알고리즘과 계산:7일 국제 워크숍 WALCOM, 2013년 카라그 푸르, 인도, 2월 14일부터 16일까지의, 2013년집, 강의 노트 컴퓨터 과학으로,, 스프링거, 7748 vol.를 대신하여 서명함. 298–309,. doi:10.1007/978-3-642-36065-7_28.
- 를 클릭합니다Doğrusöz, Uğur; Belviranli, M.; Dilek, A. (2012), "CiSE: A circular spring embedder layout algorithm", IEEE Transactions on Visualization and Computer Graphics, 19 (6): 953–966, doi:10.1109/TVCG.2012.178, hdl:11693/21006, PMID 23559509, S2CID 14365664.
- 를 클릭합니다Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Circular layout in the Graph Layout toolkit", Graph Drawing: Symposium on Graph Drawing, GD '96, Berkeley, California, USA, September 18–20, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1190, Springer, pp. 92–100, doi:10.1007/3-540-62495-3_40.
- 를 클릭합니다Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2012), "Lombardi drawings of graphs", Journal of Graph Algorithms and Applications, 16 (1): 85–108, arXiv:1009.0579, doi:10.7155/jgaa.00251.
- 를 클릭합니다Gansner, Emden R.; Koren, Yehuda (2007), Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006, Revised Papers, Lecture Notes in Computer Science, vol. 4372, Springer, pp. 386–398, doi:10.1007/978-3-540-70904-6_37.
- 를 클릭합니다He, H.; Sýkora, Ondrej (2004), "New circular drawing algorithms", Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15-19.
- 를 클릭합니다Huang, Weidong; Hong, Seok-Hee; Eades, Peter (2007), "Effects of sociogram drawing conventions and edge crossings in social network visualization", Journal of Graph Algorithms and Applications, 11 (2): 397–429, doi:10.7155/jgaa.00152.
- 를 클릭합니다Iragne, Florian; Nikolski, Macha; Mathieu, Bertrand; Auber, David; Sherman, David (2005), "ProViz: protein interaction visualization and exploration", Bioinformatics, 21 (2): 272–274, doi:10.1093/bioinformatics/bth494, PMID 15347570.
- 를 클릭합니다Krebs, Valdis (1996), "Visualizing human networks" (PDF), Release 1.0: Esther Dyson's Monthly Report, 2–96.
- 를 클릭합니다Mäkinen, Erkki (1988), "On circular layouts", International Journal of Computer Mathematics, 24 (1): 29–37, doi:10.1080/00207168808803629.
- Baur & Brandes(2005)가 인용한 바와 같이Masuda, S.; Kashiwabara, T.; Nakajima, K.; Fujisawa, T. (1987), "On the NP-completeness of a computer network layout problem", Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 292–295.
- 를 클릭합니다Nguyen, Quan; Eades, Peter; Hong, Seok-Hee; Huang, Weidong (2011), "Large crossing angles in circular layouts", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Springer, pp. 397–399, doi:10.1007/978-3-642-18469-7_40.
- 를 클릭합니다Pisanski, Tomaž; Servatius, Brigitte (2013), "2.3.2 Cubic graphs and LCF notation", Configurations from a Graphical Viewpoint, Springer, p. 32, ISBN 9780817683641.
- 를 클릭합니다Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings, Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, doi:10.1007/3-540-59071-4_53.
- 를 클릭합니다Six, Janet M.; Tollis, Ioannis G. (1999a), "Circular drawings of biconnected graphs", Algorithm Engineering and Experimentation: International Workshop ALENEX'99, Baltimore, MD, USA, January 15–16, 1999, Selected Papers, Lecture Notes in Computer Science, vol. 1619, Springer, pp. 57–73, doi:10.1007/3-540-48518-X_4.
- 를 클릭합니다Six, Janet M.; Tollis, Ioannis G. (1999b), "A framework for circular drawings of networks", Graph Drawing: 7th International Symposium, GD'99, Štiřín Castle, Czech Republic, September 15–19, 1999, Proceedings, Lecture Notes in Computer Science, vol. 1731, Springer, pp. 107–116, doi:10.1007/3-540-46648-7_11.
- Symeonidis, Alkiviadis.Tollis, 요안 니스 G.(2004년),"생물학적 정보의 원형 그림으로 가시화", 생물학적 및 의료 자료 분석:5일 국제 심포지엄, ISBMDA 2004년 스페인 바르셀로나 11월 18-19일, 2004년, 회보, 강의 노트 컴퓨터 과학으로,, 스프링거,를 대신하여 서명함 3337 vol.. 468–478, doi:10.1007/978-3-540-30547-7_47.
- 를 클릭합니다Verbitsky, Oleg (2008), "On the obfuscation complexity of planar graphs", Theoretical Computer Science, 396 (1–3): 294–300, arXiv:0705.3748, doi:10.1016/j.tcs.2008.02.032, MR 2412266, S2CID 5948167.
