우위화

Dominance drawing
우위화

우위 도면은 정점 사이의 도달성 관계를 시각적으로 뚜렷하게 만드는 지시된 반복 그래프의 그래프 그리기 스타일이다.우위 도면에서 정점은 유클리드 평면의 구별되는 지점에 배치되고 v의 두 데카르트 좌표가 u의 좌표보다 크거나 같은 경우에만 다른 정점 u에서 정점 v에 도달할 수 있다.우위 도면의 가장자리는 직선 세그먼트로 또는 경우에 따라 다각형 체인으로 그릴 수 있다.[1]

평면 그래프

그래프의 일부 내장 외면에 있는 단일 출처와 단일 싱크(sink)가 있는 방향의 AC 평면 그래프인 모든 역직구 그래프는 우위 도면을 가지고 있다.이러한 도면을 찾기 위한 왼쪽-오른쪽 알고리즘은 모든 꼭지점의 x 좌표를 그래프의 깊이 우선 검색 순서에서 위치로 설정하고, s로 시작하고 오른쪽에서 왼쪽 순서로 가장자리 우선순위를 정하며, y 좌표를 동일한 방법으로 얻되 왼쪽에서 가장자리 우선순위를 정하도록 설정한다.전형적인 우위 도면 알고리즘은 이 좌표 배정 후 다른 압축 단계를 포함하며, 우위 도면의 특성을 유지하면서 정점을 가능한 한 아래로 왼쪽으로 이동시킨다.결과 도면은 n × n 정수 격자 안에 위치하며, 기초 위상학 내장의 많은 대칭을 표시한다.이 도면, 그리고 보다 일반적으로는 전치적으로 축소된 st-planar 그래프의 모든 우위 도면은 반드시 직선 모서리를 갖는 평면이다.[1][2]

전이적으로 감소하지 않는 표준 평면 그래프의 경우, 각 가장자리를 세분화하여 동등하게 전치적으로 감소된 그래프를 얻을 수 있다.단, 결과적으로 감소된 그래프의 직선 도면은 분할에 의해 도입된 더미 정점에서 일부 가장자리가 휘어지는 원래 그래프의 도면을 형성한다.[1][2]평면 우위 도면은 일부 가장자리가 수평일 수 있기 때문에 반드시 위쪽 평면도인 것은 아니지만, 45° 회전하면 반드시 위쪽 평면도인 것이다.[1]지시된 다른 반복 그래프 그리기 방법과 비교했을 때, 좌우 알고리즘(평면화 사전 처리 단계와 함께)은 생성하는 도면의 면적, 굴곡의 수, 도면의 가로 세로 비율 측면에서 좋은 성능을 보였지만, 총 가장자리 길이에서는 덜 좋은 것으로 밝혀졌다.[3]

비계획 그래프

(평면성과 무관하게) 지시된 아세클릭 그래프에는 도달 가능성으로 정렬된 정점 집합이 순서 차원 2를 갖는 경우에만 우위 도면이 있다.(회전된) 우위 도면은 전치적으로 감소된 방향의 AC 순환 그래프를 해당 부분 순서의 Hasse 다이어그램으로 사용할 수 있다.[4]

코드금융

지시된1 Acyclic 그래프 D = (V, E1)의 우위 도면을 고려할 때, 한 축의 해석을 뒤집으면 coreachability라고 할 수 있는 새로운 관계가 된다.따라서 점(xaa, y)은 xa x x가b y가a 아니라b y가 될 때마다 점(xb, y)에서 coreachable로b 간주될 수 있다.이와 같이 지배도면을 보면 동일한 정점 집합에서 두 번째 방향의 아세클릭 그래프2 D = (V2, E)를 유도할 수 있다.도달성과 핵심성 측면에서 해석된 단일 도면에 의한 그러한 동시 표현을 허용하는 공유된 지면 집합의 부분 주문 쌍 {≤,1 ≤}2을(를) 코드민이라고 한다.[5]

약지배도

도달성 순서가 더 높은 방향의 아세클릭 그래프의 경우, 약한 우위 도면은 모든 에지가 위, 오른쪽으로 또는 둘 다 방향을 향하지만, v 좌표를 지배하지만 그래프에서 u로부터 v에 도달할 수 없는 정점 쌍(u, v)이 존재하는 도면이다.우리는 u_x, u_y의 좌표(u_x, u_y)가 v의 좌표(v_x, v_y)보다 작거나 같으면 정점 u가 또 다른 정점 v, 즉 XY 평면을 고려할 때 u_x <= v_x 및 u_y <= v_y>를 지배한다고 말했다.이런 방식의 그림 그리기의 목표는 그러한 거짓된 암묵적인 경로의 수를 최소화하는 것이다.[6]

참조

  1. ^ a b c d Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "4.7 Dominance Drawings", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 112–127, ISBN 978-0-13-301615-4.
  2. ^ a b 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.
  3. ^ Di Battista, Giuseppe; Garg, Ashim; Liotta, Giuseppe; Parise, Armando; Tamassia, Roberto; Tassinari, Emanuele; Vargiu, Francesco; Vismara, Luca (2000), "Drawing directed acyclic graphs: an experimental study", International Journal of Computational Geometry & Applications, 10 (6): 623–648, doi:10.1142/S0218195900000358, MR 1808215.
  4. ^ Baker, K. A.; Fishburn, P. C.; Roberts, F. S. (1972), "Partial orders of dimension 2", Networks, 2 (1): 11–28, doi:10.1002/net.3230020103.
  5. ^ Tanenbaum, Paul J.; Whitesides, Sue (1996), "Simultaneous dominance representation of multiple posets" (PDF), Order, 13 (4): 351–364, doi:10.1007/bf00405594, S2CID 121516733.
  6. ^ Kornaropoulos, Evgenios M.;Tollis, 요안 니스 G.(2013년),"연출한 비순환 그래프에 약한 지배 도면", Didimo, 월터;Patrignani, 마우리치오(eds.)Graph도면:20일 국제 심포지엄, 승무원 2012년, 레드먼드, WA, 미국, 9월 19-21, 2012년 7704, 스프링거,를 대신하여 서명함. 559–560, vol. 선택 기술, 강의 노트 컴퓨터 과학으로, 합치하도록 수정되었다. doi:10.1007/978-3-642-36763-2_52.