호 도표

Arc diagram
골드너-하라리 그래프의 호 다이어그램.이 그래프는 해밀턴이 아니라 빨간색 점선 세그먼트가 교차하는 가장자리를 세분화하고 이 세그먼트를 따라 두 개의 가장자리를 추가하면 해밀턴을 만들 수 있다.

호 도표는 그래프의 정점이 유클리드 평면에서 선을 따라 배치되는 그래프 그리기 스타일이며, 선으로 경계된 두 개의 반평면 중 하나 또는 둘 다에 가장자리가 반원형으로 그려지거나 반원순의 순서에 의해 형성된 부드러운 곡선으로 그려진다.어떤 경우에는 선을 따라 연속되는 정점만 연결하는 한 선 자체의 선 세그먼트도 가장자리로서 허용된다.반원형을 다른 유형의 볼록한 곡선으로 대체하는 이 그림 스타일의 변형을 흔히 호 도표라고도 한다.[1]

이러한 종류의 도면에 "아크 다이어그램"이라는 문구를 사용하는 것은 왓텐베르크(2002)가 동일한 기호의 쌍을 연결하기 위해 호를 사용함으로써 문자열의 반복 패턴을 시각화하기 위해 유사한 유형의 도표를 사용하는 것에 따른 것이다.그러나 이러한 형태의 그래프 그리기는 이름보다 훨씬 오래된 것으로, 호도를 사용하여 그래프의 교차 숫자를 연구한 사티(1964)와 니콜슨(1968)의 작품으로 거슬러 올라간다.호 다이어그램의 오래되었지만 자주 사용되지 않는 이름은 선형 임베딩이다.[2]

Heer, Bostock & Ogievetsky(2010)는 호 다이어그램이 "2차원 레이아웃만큼 효과적으로 그래프의 전체적인 구조를 전달하지 못할 수 있다"고 쓰지만, 이들의 레이아웃으로 인해 그래프의 정점과 관련된 다변량 데이터를 쉽게 표시할 수 있다고 한다.아크 다이어그램의 적용 분야에는 합리적인 숫자 사이의 숫자-이론적 연결의 시각화인 Fary 다이어그램과 다이어그램의 교차점이 구조에서 가성비를 나타내는 RNA 2차 구조를 나타내는 다이어그램이 포함된다.

평면 그래프

니콜슨(1968)이 관찰한 바와 같이, 평면 내 그래프의 모든 도면은 교차 횟수를 변경하지 않고 호 다이어그램으로 변형될 수 있다.특히 모든 평면 그래프는 평면 호 다이어그램을 가지고 있다.그러나 이 내장에는 가장자리 일부에 대해 둘 이상의 반원형을 사용해야 할 수 있다.

각 가장자리가 하나의 반원형인 호 도표를 사용하여 교차 없이 그래프를 그린다면, 그 도면은 2페이지의 책 임베딩으로, 해밀턴 이하의 그래프에만 가능한 것으로 평면 그래프의 적절한 부분집합이다.[3]예를 들어, 최대 평면 그래프는 해밀턴 사이클을 포함하는 경우에만 그러한 포함을 가진다.따라서 Goldner-Harary 그래프와 같은 해밀턴이 아닌 최대 평면 그래프는 가장자리당 반원 한 개의 평면을 갖는 평면형 내장을 가질 수 없다.주어진 그래프에 이러한 유형의 교차 자유 호 다이어그램(또는 동등하게 페이지 번호 2가 있는지 여부)이 있는지 여부를 검정하는 것은 NP-완전하다.[4]

그러나 모든 평면 그래프는 각 가장자리가 최대 2개의 반원형으로 그려진 원호도를 가지고 있다.더욱 강하게, 모든 st-평면 방향 그래프(외측 면에 모두 단일 선원과 단일 싱크가 있는 평면 방향 아세클릭 그래프)는 모든 가장자리가 단조로운 곡선을 형성하는 호 다이어그램을 가지고 있으며, 이러한 곡선은 모두 정점 선의 한쪽 끝에서 다른 쪽을 향해 일관되게 향한다.[5]비방향 평면 그래프의 경우, 가장자리당 반원수가 가장 많은 호 다이어그램을 구성하는 한 가지 방법은 그래프를 세분화하고 결과 그래프가 해밀턴 사이클을 갖도록(그리고 각 가장자리가 한 번에 분할되도록) 추가 에지를 추가하는 것이며, 해밀턴 사이클에서 정점의 순서를 선에 따른 순서로 사용하는 것이다..[6] 정점이 개인 평면 그래프에서는 최대 / 2 n개의 생물체가 필요하다.[7]

교차 최소화

주어진 그래프에 에지당 반원 1개가 있고 교차점이 없는 원호도가 있는지 여부를 검정하는 것이 NP-완전하므로 교차 횟수를 최소화하는 이 유형의 원호도를 찾는 것도 NP-강력하다.이 교차 최소화 문제는 선을 따라 정점의 순서가 고정되어 있더라도 비 평면 그래프의 경우 NP-hard로 남아 있다.[2]그러나 고정순서의 경우, 교차 없는 내장(존재하는 경우)을 다항 시간 내에 각 호의 배치를 나타내는 변수 및 제약조건이 교차 호를 정점선의 같은 쪽에 배치하지 못하도록 하는 2만족성 문제로 번역하여 발견할 수 있다.[8]또한 고정 순서의 경우 교차 축소 임베딩은 세미클과 잠재적 교차(또는 동등하게, 2-만족성 인스턴스의 MAX2SAT 버전)를 나타내는 보조 그래프에서 최대 절단 문제를 해결함으로써 근사치를 구할 수 있다.[9]

시미코프스키&쇼페(1996년), 시미코프스키(2002년), 헤, 소코라&브르토(2005년)는 교차점이 거의 없는 호 도표를 찾기 위한 휴리스틱스를 논한다.

시계방향

지시된 그래프의 도면의 경우, 공통적인 관례는 각 호를 시계방향으로 그려서, 배열의 초기 정점부터 후자의 정점까지의 호를 정점선 위로 그리고 후자의 정점부터 초기 정점까지의 호를 선 아래로 그리는 것이다.이 시계 방향 규약은 Fekette 등이 다른 그래프 그리기 스타일의 일부로 개발했다. (2003년), 그리고 프레토리오스 & 반 바이크(2007)가 호 다이어그램에 적용했다.

적용들

페어리 다이어그램

합리적인 숫자의 집합의 Fary 다이어그램은 호 다이어그램으로 기하학적으로 표현될 수 있는 구조다.이 형식에서 숫자 선에 배치된 각 숫자에 대한 꼭지점과 과 간단한 용어로 p- = 1 쌍을 연결하는 선 위의 반원형 가장자리가 있다다이어그램의 반원형은 쌍곡면의 푸앵카레 반평면 모델의 선으로 생각할 수 있으며, 정점은 이 모델의 경계선에 무한한 지점에 위치한다.푸앵카레 반평면 모델은 모델 내 모든 수직선의 공유 끝점인 경계선의 점으로 표현되지 않는 무한점을 가지고 있으며, 이것은 부속성을 결정하는 데 동일한 규칙으로 "굴절" 1/0(숫자로 정의되지 않음)으로 표현될 수 있다.합리적인 숫자의 집합에 대한 Fary 다이어그램은 평면 그래프로, 모든 합리적인 숫자의 집합에 대한 Fary 다이어그램은 이상적인 삼각형에 의한 쌍곡면의 다듬기를 형성한다.[10]

호 도표는 RNA 시퀀스 또는 기타 생물학적 중합체의 염기쌍 사이의 결합을 시각화하는 데 사용될 수 있으며, 도표 선을 따라 배열된 염기서열의 염기서열 및 비애드자이스임에도 불구하고 폴리머의 물리적 구조에 인접해 있는 염기들 사이의 결합을 나타내는 선 위의 호를 사용할 수 있다.순서에 따라 nt.이차 구조가 내포된 스템과 루프로 구성된 시퀀스의 경우 호 다이어그램에는 교차점이 없다.교차점이 있을 때, 교차점은 구조에서 가성비를 나타낸다.호와 교차점의 교차 그래프의 정도 분포는 폴리머의 위상학적 특징의 스케일링 동작을 이해하는 데 사용될 수 있다.[11]

Brandes(1999년)는 교대장의 상태 다이어그램을 시각화하기 위해, Jidjev & Vrto(2002년)는 모든 그래프의 교차 번호가 Byrne 외 연구진의 절단폭과 정점도의 조합에 의해 더 낮은 경계임을 보여주기 위해 사용하였다. (2007) 블루투스 장치 간의 상호작용을 시각화하고, 오웬스 & 얀쿤-켈리(2013)가 미식축구 경기에서 플레이의 야디지를 시각화한다.이 시각화 기법의 추가 적용은 Nagel & Duval(2013)이 조사한다.

메모들

  1. ^ 나겔 & 듀발(2013년).
  2. ^ a b 마스다 외 연구진(1990).
  3. ^ 책 임베딩에서 반원형을 가장자리에 적용하는 것은 이미 베른하르트&카인엔(1979년)에 의해 이루어졌지만, 호 도표를 2페이지의 책 임베딩과 명시적으로 연결하는 것은 마스다 외 연구진(1990년)에 의한 것으로 보인다.
  4. ^ 정, 레이튼 & 로젠버그(1987년).
  5. ^ 지오다노 외 (2007).
  6. ^ 베코스 외(2013년).
  7. ^ 추기경 외(2018년).
  8. ^ 에프랫, 에르텐 & 코부로프(2007)
  9. ^ 시미코프스키 & 무메이(2007)
  10. ^ 길만앤킨(2002년).
  11. ^ 카바크소울루&스텔라(2005년).

참조

  • Bekos, 마이클 A.;카우프만, 마이클 Kobourov, 스티븐 G.;Symvonis, 안토니오스(2013년),"직교 레이아웃 원활한"Graph도면:20일 국제 심포지엄, 승무원 2012년, 레드먼드, WA, 미국, 9월 19–21, 2012년 7704, 스프링거, pp vol.. 선택된 논문, 강의 노트 컴퓨터 과학으로, 150–161, doi:10.1007/978-3-642-36763-2_14, 아이 에스비엔 978-3- 합치하도록 수정되었다.642-36762-5.
  • Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2.
  • Brandes, Ulrik (1999), "Hunting down Graph B", 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. 410–415, doi:10.1007/3-540-46648-7_42, ISBN 978-3-540-66904-3.
  • 번, Daragh, 라벨은 말했는데, 배리, 존스, 가레스 JF;스미턴, AlanF.(2007년),"Visualising 블루투스 상호 작용:DocuBurst 기술이 아크도 결합"(PDF), Ormerod, 토마스 C.;샤슈, Corina(eds.), 회보에 21영국 HCI그룹 연차 회의에 HCI2007년:HCI... 하지만 우리가 알고 있는-볼륨 2, BCSHCI2007년, Univer.Sity의, 영국, 3-72007년 9월, 영국 컴퓨터 학회,를 대신하여 서명함. 129–132.
  • Cardinal, Jean; Hoffmann, Michael; Kusters, Vincent; Tóth, Csaba D.; Wettstein, Manuel (2018), "Arc diagrams, flip distances, and Hamiltonian triangulations", Computational Geometry, 68: 206–225, arXiv:1611.02541, doi:10.1016/j.comgeo.2017.06.001, MR 3715053, S2CID 1169465
  • Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design" (PDF), SIAM Journal on Algebraic and Discrete Methods, 8 (1): 33–58, doi:10.1137/0608002.
  • Cimikowski, Robert (2002), "Algorithms for the fixed linear crossing number problem", Discrete Applied Mathematics, 122 (1–3): 93–115, doi:10.1016/S0166-218X(01)00314-6, MR 1907825.
  • Cimikowski, Robert; Mumey, Brendan (2007), "Approximating the fixed linear crossing number", Discrete Applied Mathematics, 155 (17): 2202–2210, doi:10.1016/j.dam.2007.05.009, MR 2360650.
  • Cimikowski, Robert; Shope, Paul (1996), "A neural-network algorithm for a graph layout problem", IEEE Transactions on Neural Networks, 7 (2): 341–345, doi:10.1109/72.485670, PMID 18255588.
  • Djidjev, Hristo; Vrt'o, Imrich (2002), "An improved lower bound for crossing numbers", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2265, Springer, pp. 96–101, doi:10.1007/3-540-45848-4_8, ISBN 978-3-540-43309-5.
  • Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), "Fixed-location circular arc drawing of planar graphs", Journal of Graph Algorithms and Applications, 11 (1): 145–164, doi:10.7155/jgaa.00140.
  • Fekete, Jean-Daniel; Wang, David; Dang, Niem; Aris, Aleks; Plaisant, Catherine (2003), "Overlaying graph links on treemaps", IEEE Symp. on Information Visualization, Poster Compendium, pp. 82–83.
  • Gilman, Jane; Keen, Linda (2002), "Word sequences and intersection numbers" (PDF), Complex manifolds and hyperbolic geometry (Guanajuato, 2001), Contemporary Mathematics, vol. 311, Providence, Rhode Island: American Mathematical Society, pp. 231–249, doi:10.1090/conm/311/05455, MR 1940172; 섹션 2.4 "Pary diagraphes and continuous fractures" 참조
  • 조르다노, 프란체스코, 리오타, 주세페;Mchedlidze, 타마라, Symvonis, 안토니오스(2007년),"상승 평면 digraphs의 위로 위상 책 embeddings을 산출하는", 알고리즘과 계산:18일 국제 심포지엄, 아이작 2007년, 센다이, 일본, 12월 17일부터 19일까지, 2007, 회보, 강의 노트 컴퓨터 과학으로,. 172–183, 4835, 스프링거,를 대신하여 서명함 vol.. doi:10.1007/978-3-540-77120-3_17, 아이 에스비엔 978-3-540-77118-0.
  • He, Hongmei; Sýkora, Ondrej; Vrt'o, Imrich (2005), "Crossing Minimisation Heuristics for 2-page Drawings", Electronic Notes in Discrete Mathematics, 22: 527–534, doi:10.1016/j.endm.2005.06.088.
  • Heer, Jeffrey; Bostock, Michael; Ogievetsky, Vadim (2010), "A tour through the visualization zoo", Communications of the ACM, 53 (6): 59–67, doi:10.1145/1743546.1743567.
  • Kabakçıoğlu, A.; Stella, A. L. (November 2005), "Scale-free network hidden in a collapsing polymer", Physical Review E, 72 (5), 055102(R), arXiv:cond-mat/0409584, Bibcode:2005PhRvE..72e5102K, doi:10.1103/physreve.72.055102, PMID 16383674, S2CID 29977757
  • Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers, 39 (1): 124–127, doi:10.1109/12.46286, MR 1032144.
  • Nagel, Till; Duval, Erik (2013), "A visual survey of arc diagrams" (PDF), 2013 VIS Posters, IEEE
  • Nicholson, T. A. J. (1968), "Permutation procedure for minimising the number of crossings in a network", Proceedings of the Institution of Electrical Engineers, 115: 21–26, doi:10.1049/piee.1968.0004, MR 0311416.
  • Owens, Sean Gabriel; Jankun-Kelly, T. J. (2013), "Visualizations for exploration of American football season and play data" (PDF), 1st IEEE VIS Workshop on Sports Data Visualization, IEEE
  • Pretorius, A. J.; van Wijk, J. J. (2007), "Bridging the semantic gap: Visualizing transition graphs with user-defined diagrams", IEEE Computer Graphics and Applications, 27 (5): 58–66, doi:10.1109/MCG.2007.121, PMID 17913025, S2CID 8643133.
  • Saaty, Thomas L. (1964), "The minimum number of intersections in complete graphs", Proceedings of the National Academy of Sciences of the United States of America, 52 (3): 688–690, Bibcode:1964PNAS...52..688S, doi:10.1073/pnas.52.3.688, MR 0166772, PMC 300329, PMID 16591215.
  • Wattenberg, M. (2002), "Arc diagrams: visualizing structure in strings", Proc. IEEE Symposium o nInformation Visualization (INFOVIS 2002), pp. 110–116, doi:10.1109/INFVIS.2002.1173155, ISBN 0-7695-1751-X, S2CID 881989.