그래프 그리기

Graph drawing
이 기사는 그래프 그리기의 일반적인 주제에 관한 것이다.연례 연구 심포지엄은 그래프 그리기 국제 심포지엄을 참조하십시오.
하이퍼링크를 나타내는 WWW의 미세한 부분을 그래픽으로 나타냅니다.

그래프 드로잉(graph drawing)은 기하학 그래프 이론과 정보 시각화 방법을 결합하여 소셜 네트워크 분석,[1] 지도 제작, 언어학 및 생물 정보학 등의 애플리케이션에서 발생하는 그래프의 2차원 묘사를 도출하는 수학 및 컴퓨터 과학 분야입니다.

그래프 또는 네트워크 다이어그램은 그래프의 정점과 모서리를 그림으로 표현한 것입니다.이 도면은 그래프 자체와 혼동해서는 안 됩니다. [2]같은 그래프에 매우 다른 레이아웃이 대응될 수 있습니다.요약에서 중요한 것은 어떤 정점 쌍이 모서리에 의해 연결되느냐입니다.그러나 구체적으로는 도면 내에서 이러한 정점과 모서리의 배열이 이해성, 사용성, 제작 비용 및 [3]미학에 영향을 미칩니다.시간이 지남에 따라 가장자리를 추가 및 삭제하고(동적 그래프 그리기) 그래프가 변경되어 사용자의 멘탈 [4]맵을 보존하는 것이 목적이라면 문제는 더욱 심각해집니다.

그래피컬 표기법

모서리 방향을 나타내는 화살촉이 있는 방향 그래프

그래프는 정점이 디스크, 상자 또는 텍스트 레이블로 표시되고 가장자리가 유클리드 [3]평면에서 선분, 폴리선 또는 곡선으로 표시되는 노드 링크 다이어그램으로 자주 그려집니다.노드 링크 다이어그램은 13세기 폴리매스인 라몬 룰(Ramon Lull)의 이름으로 출판된 14-16세기 유사-룰(Pseudo-Lull)Pseudo-Lull은 형이상학적 [5]개념 세트 간의 모든 쌍별 조합을 분석하기 위해 완전한 그래프에 대해 이 유형의 다이어그램을 그렸다.

방향 그래프의 경우 화살촉은 방향을 [2]나타내기 위해 일반적으로 사용되는 그래픽 규칙을 형성하지만, 사용자 연구에 따르면 테이퍼링과 같은 다른 규칙이 이 정보를 [6]더 효과적으로 제공하는 것으로 나타났습니다.위쪽 평면 도면에서는 모든 가장자리가 아래쪽 정점에서 높은 정점으로 향하므로 화살촉이 필요하지 않습니다.[7]

노드 링크 다이어그램의 대체 표기법에는 평면에서 정점이 분리된 영역으로 표현되고 가장자리가 영역 간의 인접으로 표현되는 원 패킹과 같은 인접 표현이 포함된다. 정점이 비연속 기하학적 객체로 표현되고 가장자리가 표현되는 교차 표현은 다음과 같다.교차점에 의한 ed, 정점이 평면에서 영역으로 표현되는 가시성 표현, 가장자리가 서로에 대해 방해받지 않는 시선선을 갖는 영역으로 표현되는 합류 도면, 노드가 h로 표현되는 직물수직선으로서의 수평선 [8]및 모서리, 그래프의 인접 행렬 시각화.

품질 측정

그래프 도면의 미학과 사용성을 [9]평가하는 객관적인 방법을 찾기 위해 그래프 도면에 대해 많은 다른 품질 측정이 정의되었다.동일한 그래프에 대해 다른 레이아웃 방법 간의 선택을 안내할 뿐만 아니라, 일부 레이아웃 방법은 이러한 측정을 직접 최적화하려고 시도합니다.

겹치는 모서리 없이 그려진 평면 그래프
  • 도면의 교차 번호는 서로 교차하는 모서리 쌍의 수입니다.그래프가 평면인 경우 가장자리 교차점 없이 그리는 것이 편리합니다. 즉, 그래프 그림은 그래프 삽입을 나타냅니다.그러나 비평면 그래프는 응용 프로그램에서 자주 발생하므로 그래프 그리기 알고리즘은 일반적으로 가장자리 [10]교차를 허용해야 합니다.
  • 도면의 면적은 두 정점 사이의 가장 가까운 거리에 상대적인 가장 작은 경계 상자의 크기입니다.일반적으로 면적이 작은 도면은 면적이 큰 도면에 비해 선호됩니다. 도면의 특징을 더 큰 크기로 표시하기 때문에 더 읽기 쉽게 할 수 있기 때문입니다.경계 상자의 가로 세로 비율도 중요할 수 있습니다.
  • 대칭 표시는 주어진 그래프 내에서 대칭 그룹을 찾고 가능한 한 대칭을 많이 표시하는 도면을 찾는 문제입니다.일부 배치 방법은 자동으로 대칭 도면으로 이어집니다. 또는 일부 도면 방법은 입력 그래프에서 대칭을 찾아 [11]도면을 구성하는 것으로 시작합니다.
  • 가장자리에 가능한 한 단순한 모양을 갖는 것이 중요합니다. 그러면 눈이 가장자리를 따라하기 쉬워집니다.폴리선 도면의 경우 모서리의 복잡도는 벤딩 수로 측정할 수 있으며, 많은 방법에서 전체 벤딩 또는 모서리당 벤딩 수가 적은 도면을 제공하는 것을 목적으로 합니다.마찬가지로 스플라인 곡선의 경우 가장자리의 복잡도는 가장자리의 제어점 수로 측정할 수 있습니다.
  • 일반적으로 사용되는 몇 가지 품질 측정은 가장자리 길이에 관한 것입니다. 일반적으로 모든 가장자리의 최대 길이는 물론 전체 가장자리 길이를 최소화하는 것이 좋습니다.또한, 높은 변동보다는 가장자리의 길이가 균일한 것이 바람직할 수 있다.
  • 각도 분해능은 그래프 도면에서 가장 날카로운 각도의 척도입니다.그래프에 높은 도수의 정점이 있는 경우 반드시 작은 각도 분해능을 가지지만 각도 분해능은 아래의 [12]도 함수에 의해 제한될 수 있습니다.
  • 그래프의 기울기 번호는 직선 세그먼트 모서리가 있는 도면에 필요한 고유한 모서리 기울기의 최소 수입니다(교차를 허용).입방형 그래프에는 최대 4개의 기울기 번호가 있지만 5도의 그래프에는 무제한 기울기 번호가 있을 수 있습니다. 4도 그래프의 기울기 번호가 경계가 [12]되어 있는지 여부는 열려 있습니다.

레이아웃 방법

강제 기반 네트워크 시각화.[13]

다양한 그래프 레이아웃 전략이 있습니다.

  • 힘에 기초한 레이아웃 시스템에서 그래프 그리기 소프트웨어는 스프링 또는 분자역학과 관련된 물리적 은유에 기초한 힘의 시스템에 따라 정점을 연속적으로 이동시킴으로써 초기 정점 배치를 변경한다.일반적으로 이러한 시스템은 인접한 정점 사이의 흡인력과 모든 정점 쌍 사이의 반발력을 결합하여 정점이 잘 분리된 반면 가장자리 길이가 작은 레이아웃을 추구한다.이러한 시스템은 에너지 함수의 경사 강하 기반 최소화를 수행하거나 움직이는 [14]정점에 대한 속도 또는 가속으로 직접 힘을 변환할 수 있습니다.
  • 스펙트럼 레이아웃 방법은 그래프의 [15]인접 행렬에서 파생된 라플라시안과 같은 행렬의 고유 벡터를 좌표로 사용한다.
  • 그래프의 모서리가 레이아웃의 좌표 축에 평행하게 수평 또는 수직으로 실행될 수 있도록 하는 직교 레이아웃 방법입니다.이러한 방법은 원래 VLSI 및 PCB 레이아웃 문제를 위해 설계되었지만 그래프 그리기에도 적용되었습니다.일반적으로 교차점을 정점으로 대체하여 입력 그래프를 평탄화시키고, 평탄화 그래프의 위상 매립을 찾고, 굴곡을 최소화하기 위해 가장자리 방향을 선택하고, 정점을 이러한 방향과 일관되게 배치하고, 마지막으로 배치 압축 단계를 통해 th의 면적을 감소시키는 다단계 접근법을 포함한다.e [16]도면
  • 트리 레이아웃 알고리즘은 나무에 적합한 루트 트리 형성을 보여줍니다.종종 "풍선 배치"라고 불리는 기술에서는 트리의 각 노드의 자녀가 노드를 둘러싼 원에 그려지며, 이러한 원의 반지름은 트리의 낮은 수준에서 감소하여 이러한 원이 [17]겹치지 않도록 합니다.
  • 레이어드 그래프 그리기 방법(종종 스기야마 스타일 그리기라고 함)은 소프트웨어 시스템의 모듈 또는 함수 간 종속성 그래프와 같이 거의 비순환적인 방향성 비순환 그래프 또는 그래프에 가장 적합합니다.이러한 방법에서 그래프의 노드는 Coffman-Graham 알고리즘과 같은 방법을 사용하여 수평 레이어로 배열되며, 대부분의 가장자리가 한 레이어에서 다음 레이어로 내려가는 방식으로 배열됩니다. 이 단계 이후 각 레이어 내의 노드는 [18]교차를 최소화하기 위해 배열됩니다.
호도
  • 1960년대부터 [19]시작된 배치 스타일인 호 다이어그램은 정점을 선 위에 배치합니다. 가장자리는 선의 위 또는 아래에 반원으로 그리거나 여러 개의 반원에서 서로 연결된 부드러운 곡선으로 그릴 수 있습니다.
  • 원형 레이아웃 방법은 그래프의 정점을 원에 배치하고 교차를 줄이고 인접한 정점을 서로 가깝게 배치하기 위해 원 주위의 정점 순서를 신중하게 선택합니다.모서리는 원의 현 또는 원의 내부 또는 외부 호로 그릴 수 있습니다.경우에 따라 여러 개의 원이 [20]사용될 수 있습니다.
  • 우세 도면은 한 정점이 다른 정점에서 도달할 수 있는 경우에만 위, 오른쪽 또는 다른 정점의 둘 다에 위치하도록 정점을 배치합니다.이와 같이 레이아웃 스타일은 그래프의 도달 가능성 관계를 시각적으로 명확하게 [21]한다.

응용 프로그램별 그래프 도면

응용 프로그램의 다른 영역에서 발생하는 그래프 및 그래프 도면에는 다음이 포함됩니다.

또한 전자설계자동화(EDA)의 배치 및 라우팅 단계는 분산 컴퓨팅에서의 탐욕적 임베딩 문제와 마찬가지로 그래프 도면과 여러 면에서 유사하며 그래프 도면 문헌은 EDA 문헌에서 차용한 여러 결과를 포함한다.단, 이러한 문제는 몇 가지 중요한 방법으로도 다릅니다.예를 들어 EDA에서는 면적 최소화 및 신호 길이가 미학보다 중요하며 EDA의 라우팅 문제는 네트당 2개 이상의 단자가 있는 반면 그래프 그리기에서는 일반적으로 각 엣지의 정점 쌍만 관련됩니다.

소프트웨어

그래프 그리기 인터페이스(Gephi 0.9.1)

그래프를 그리기 위한 소프트웨어, 시스템 및 시스템 공급자는 다음과 같습니다.

  • 노드를 수평선으로 그려 대규모 네트워크를 시각화하는 BioFabric 오픈 소스 소프트웨어입니다.
  • Cytoscape, 분자 상호 작용 네트워크를 시각화하는 오픈 소스 소프트웨어
  • Gephi, 오픈 소스 네트워크 분석 및 시각화 소프트웨어
  • graph-tool, 그래프 분석용 프리/라이브 Python 라이브러리입니다.
  • AT&T사의[28] 오픈소스 그래프 그리기 시스템 Graphviz
  • Linkurious, 그래프 데이터베이스용 상용 네트워크 분석 및 시각화 소프트웨어
  • Mathematica는 2D 및 3D 그래프 시각화 [29][30]및 그래프 분석 도구를 포함하는 범용 계산 도구입니다.
  • Microsoft Automatic Graph Layout, 오픈소스.그래프를 배치하기[31] 위한 NET 라이브러리(구칭 GLEE)
  • NetworkX는 그래프와 네트워크를 연구하기 위한 Python 라이브러리입니다.
  • 오픈 소스 데이터 시각화 도구인 Tulip(소프트웨어)[32]
  • 그래프 레이아웃[33] 기능이 있는 그래프 편집기 yEd
  • PGF/TikZ 3.0 및graphdrawing패키지(LuaTeX [34]필요)
  • 오픈 소스 대규모 네트워크 시각화 소프트웨어인 LaNet-vi
  • Edraw Max 2D 비즈니스 기술 다이어그램 소프트웨어

「 」를 참조해 주세요.

레퍼런스

각주
  1. ^ Di Battista et al.(1994), 페이지 vii-8; Herman, Melanson & Marshall(2000), 섹션 1.1, "일반적인 적용 영역"
  2. ^ a b 디 바티스타 외 연구진(1994), 페이지 6.
  3. ^ a b 디 바티스타 외 연구진(1994), 페이지 8.
  4. ^ Misue 등(1995년)
  5. ^ 를 클릭합니다Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37.
  6. ^ Holten & van Wijk (2009);Holten et al. (2011년)
  7. ^ Garg & Tamassia (1995).
  8. ^ Longabaugh(2012).
  9. ^ Di Battista et al.(1994), 섹션 2.1.2, 미학, 페이지 14-16; 구매, Cohen & James(1997).
  10. ^ 디 바티스타 외 연구진(1994), 페이지 14.
  11. ^ 디 바티스타 외 연구진(1994), 페이지 16.
  12. ^ a b Pach & Sharir (2009년).
  13. ^ 출판일
  14. ^ 디 바티스타 외 연구진(1994년), 섹션 2.7, "힘 지향적 접근법", 페이지 29-30, 10장 "힘 지향적 방법", 페이지 303-326.
  15. ^ Beckman(1994년), Koren(2005년).
  16. ^ Di Battista et al.(1994), 5장, "흐름과 직교 도면", 137–170; 페이지 (Eiglsperger, Fekete & Klau 2001)
  17. ^ Herman, Melanson 및 Marshall(2000), 섹션 2.2, "기존 레이아웃 – 개요"
  18. ^ 스기야마, 타가와, 토다(1981년); 바스터트 & 마투셰프스키(2001년);Di Battista et al.(1994), 제9장, "디그래프의 층화도", 265–302페이지.
  19. ^ 사티(1964).
  20. ^ Dozrusöz, Madden & Madden(1997).
  21. ^ Di Battista et al.(1994), 섹션 4.7, "우위 도면", 112–127페이지.
  22. ^ Scott(2000년), Brandes, Freeman & Wagner(2014년).
  23. ^ 디 바티스타 외 연구진(1994년), 페이지 15-16 및 6장, "흐름과 상향 평탄성", 페이지 171-214; 프리즈(2004년).
  24. ^ Zapponi(2003년).
  25. ^ Anderson & Head (2006)
  26. ^ Di Battista & Remotedini (2014).
  27. ^ Bachmaier, Brandes & Schreiber (2014).
  28. ^ "Graphviz and Dynagraph – Static and Dynamic Graph Drawing Tools", John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C.노스, 고든 우드헐(2004년)의 귄거&머첼.
  29. ^ GraphPlot Mathematica 문서
  30. ^ 그래프 그리기 튜토리얼
  31. ^ Nachmanson, Robertson & Lee (2008).
  32. ^ Jünger & Mutzel(2004)의 David Auber의 "Tulip – A Harge Graph Visualization Framework" (툴립 – 거대한 그래프 시각화 프레임워크)
  33. ^ Roland Wiese, Markus Eiglsperger 및 Michael Kaufmann의 "yFiles – 시각화와 그래프의 자동 레이아웃"(2004년)
  34. ^ Tantau(2013), 이전 GD 2012 프리젠테이션도 참조
일반 참고 자료
전문 서브토픽
  • 를 클릭합니다Anderson, James Andrew; Head, Thomas J. (2006), Automata Theory with Modern Applications, Cambridge University Press, pp. 38–41, ISBN 978-0-521-84887-9.
  • 를 클릭합니다Bachmaier, Christian; Brandes, Ulrik; Schreiber, Falk (2014), "Biological Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 621–651.
  • 를 클릭합니다Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0.
  • 를 클릭합니다Beckman, Brian (1994), Theory of Spectral Graph Layout, Tech. Report MSR-TR-94-04, Microsoft Research.
  • 를 클릭합니다Brandes, Ulrik; Freeman, Linton C.; Wagner, Dorothea (2014), "Social Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 805–839.
  • 를 클릭합니다Di Battista, Giuseppe; Rimondini, Massimo (2014), "Computer Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 763–803.
  • Doğrusöz, Uğur, 매든, 브렌던, 매든, 패트릭(1997년),"Graph레이아웃 툴 키트 원형으로 된 레이아웃", 북한에서 스티븐(교육.), 심포지엄 Graph도면, GD'96 버클리, 캘리포니아, 미국, 9월 18–20, 1996, 회보에, 강의 노트 컴퓨터 과학으로, 1190년, Springer-Verlag, vol.를 대신하여 서명함. 92–100, doi:10.1007/3-540-62495-3_40, 아이 에스비엔 978-3-540-62.495-0.
  • 를 클릭합니다Eiglsperger, Markus; Fekete, Sándor; Klau, Gunnar (2001), "Orthogonal graph drawing", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs, Lecture Notes in Computer Science, vol. 2025, Springer Berlin / Heidelberg, pp. 121–171, doi:10.1007/3-540-44969-8_6, ISBN 978-3-540-42062-0.
  • 프리스, 랄프(2004년),"자동화 격자 그리기", Eklund에, 피터(교육.), 개념 Lattices:.둘째 국제 회의 공식적인 개념 분석에, ICFCA 2004년, 시드니, 호주, 2월 23일부터 26일까지, 2004년, 저자(PDF), 강의 노트 컴퓨터 과학으로, 2961, Springer-Verlag, pp vol.. 589–590, CiteSeerX 10.1.1.69.6245, doi:10.1007/978-3-540-24651-0_12, 아이 에스비엔 978-3-540-21043-6.
  • 를 클릭합니다Garg, Ashim; Tamassia, Roberto (1995), "Upward planarity testing", Order, 12 (2): 109–133, CiteSeerX 10.1.1.10.2237, doi:10.1007/BF01108622, MR 1354797, S2CID 14183717.
  • Holten, 대니, Isenberg, 페트라, 반 Wijk, Jarke J.;페케테, Jean-Daniel(2011년),"애니메이션, 직조했었다 테이퍼directed-edge 표현의 가독성의node-link 그래프에서 확장 평가"IEEE태평양 시각화 심포지엄(PacificVis 2011년)(PDF),를 대신하여 서명함. 195–202, doi:10.1109/PACIFICVIS.2011.5742390, 아이 에스비엔 978-1-61284-935-5, S2CI.D 16526781.
  • Holten, 대니, 반 Wijk, Jarke J.(2009년),"시각화한 가장자리에 그래프의 이용자 연구", 27국제 회의 인간 요인에 컴퓨팅 시스템에 회보(CHI '09)(PDF),를 대신하여 서명함. 2299–2308, CiteSeerX 10.1.1.212.5461, doi:10.1145/1518701.1519054, 아이 에스비엔 9781605582467, S2CID 9725345, 2011-1에 있는 원본(PDF)에서 보관.1-06.
  • 를 클릭합니다Koren, Yehuda (2005), "Drawing graphs by eigenvectors: theory and practice", Computers & Mathematics with Applications, 49 (11–12): 1867–1888, doi:10.1016/j.camwa.2004.08.015, MR 2154691.
  • 를 클릭합니다Longabaugh, William (2012), "Combing the hairball with BioFabric: a new approach for visualization of large networks", BMC Bioinformatics, 13: 275, doi:10.1186/1471-2105-13-275, PMC 3574047, PMID 23102059.
  • 매든, 브렌던, 매든, 패트릭, 파워, 스티브, Himsolt, 마이클(1996년),"휴대용 그래프 레이아웃 및 편집", 브란덴부르크에, 프란츠 J.(교육.)Graph도면:.심포지엄 Graph도면에 GD95, 파사우, 독일, 9월 20–22, 1995년, 회보, 강의 노트 컴퓨터 과학으로, vol. 1027년, Springer-Verlag,를 대신하여 서명함. 385–395, doi:10.1007/BFb0021822, 아이 에스비엔 978-3-540-60723-6.
  • 를 클릭합니다Misue, K.; Eades, P.; Lai, W.; Sugiyama, K. (1995), "Layout Adjustment and the Mental Map", Journal of Visual Languages & Computing, 6 (2): 183–210, doi:10.1006/jvlc.1995.1010.
  • Nachmanson, 레프, 로버트슨, 조지, 대통령, Bongshin(2008년),"GLEE과 Graphs 그리는"(PDF), 홍, Seok-Hee에;Nishizeki, 다카오, 권, 우(eds.)Graph도면, 15일 국제 심포지엄, GD2007년, 시드니, 호주, 9월 24–26, 2007, 수정된 논문, 강의 노트 컴퓨터 과학으로, Springer-Verlag,를 대신하여 서명함. 389–394, 4875 vol.. 도이:10.1007/978-3-540-77537-9_38, 아이 에스비엔 978-3-540-77536-2[영구적인 죽은 링크].
  • 를 클릭합니다Pach, János; Sharir, Micha (2009), "5.5 Angular resolution and slopes", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.
  • 를 클릭합니다Purchase, H. C.; Cohen, R. F.; James, M. I. (1997), "An experimental study of the basis for graph drawing algorithms" (PDF), Journal of Experimental Algorithmics, 2, Article 4, doi:10.1145/264216.264222, S2CID 22076200[permanent dead link].
  • 를 클릭합니다Saaty, Thomas L. (1964), "The minimum number of intersections in complete graphs", Proc. Natl. Acad. Sci. U.S.A., 52 (3): 688–690, Bibcode:1964PNAS...52..688S, doi:10.1073/pnas.52.3.688, PMC 300329, PMID 16591215.
  • 를 클릭합니다Scott, John (2000), "Sociograms and Graph Theory", Social network analysis: a handbook (2nd ed.), Sage, pp. 64–69, ISBN 978-0-7619-6339-4.
  • 를 클릭합니다Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Methods for visual understanding of hierarchical system structures", IEEE Transactions on Systems, Man, and Cybernetics, SMC-11 (2): 109–125, doi:10.1109/TSMC.1981.4308636, MR 0611436, S2CID 8367756.
  • 를 클릭합니다Tantau, Till (2013), "Graph Drawing in TikZ", Journal of Graph Algorithms and Applications, 17 (4): 495–513, doi:10.7155/jgaa.00301.
  • 를 클릭합니다Zapponi, Leonardo (August 2003), "What is a Dessin d'Enfant" (PDF), Notices of the American Mathematical Society, 50: 788–789.

외부 링크