평탄도 테스트

Planarity testing

그래프 이론에서 평탄도 테스트 문제는 주어진 그래프가 평면 그래프인지 아닌지를 테스트하는 알고리즘 문제입니다(즉, 모서리 교차점이 없는 평면에 그릴 수 있는지 여부).이것은 컴퓨터 과학에서 잘 연구된 문제이며, 많은 실용적인 알고리즘이 등장했으며, 많은 알고리즘이 새로운 데이터 구조를 이용하고 있다.이러한 방법 대부분은 O(n) 시간(선형 시간)에 작동하며, 여기서 n은 그래프에서 점근적으로 최적의 에지(또는 정점) 수입니다.평탄도 테스트 알고리즘의 출력은 단순히 단일 부울 값이 아니라 평탄도인 경우에는 평탄도 그래프 임베딩이거나 평탄도인 경우에는 쿠라토스키 하위 그래프와 같은 평탄도에 대한 장애물이 될 수 있다.

평면성 기준

평면성 테스트 알고리즘은 일반적으로 그래프 도면에 독립적인 관점에서 평면 그래프 집합을 특징짓는 그래프 이론의 이론들을 이용한다.여기에는 다음이 포함됩니다.

Fraysseix-Rosenstiehl 평탄도 기준은 평탄도 테스트를 위한 알고리즘의 일부로 직접 사용할 수 있는 반면, Kuratowski와 Wagner의 이론에는 간접적인 적용이 있다. 알고리즘이 주어진 그래프 내에서 K 또는3,3 K의 복사본을5 찾을 수 있다면 입력 그래프가 평면이 아니며 추가 계산 없이 반환되는 것을 확인할 수 있다.

평면 그래프를 수학적으로 특성화하지만 평면성 테스트 알고리즘에 덜 중심적인 다른 평면성 기준은 다음과 같다.

알고리즘

경로 추가 방법

Hopcroft와[1] Tarjan의 고전적인 경로 추가 방법은 1974년에 최초로 발표된 선형 시간 평탄도 테스트 알고리즘이었다.Hopcroft와 Tarjan의 알고리즘 실장은 Mehlhorn, Mutzel 및 [2][3][4]Néher의 효율적인 데이터 타입과 알고리즘 라이브러리에 있습니다.2012년, 테일러는[5] 이 알고리즘을 확장하여 쌍커넥트 구성 요소의 평면 임베딩을 위한 순환 에지 순서의 모든 순열을 생성했다.

정점 가산법

정점 가산 방법은 주어진 그래프의 유도 서브그래프의 가능한 임베딩을 나타내는 데이터 구조를 유지하고 이 데이터 구조에 정점을 한 번에 하나씩 추가함으로써 작동한다.이 방법들은 [6]1967년 렘펠, 이븐, 세더바움이 고안한 비효율적인 O2(n) 방법에서 시작되었다.s, t 번호 [7]부여 단계를 위한 선형 시간 솔루션을 발견한 Even과 Tarjan, PQ 트리 데이터 구조를 개발한 Booth와 Lueker에 의해 개선되었다.이러한 개선으로 인해 선형 시간이 되며 [8]실제로 경로 추가 방법을 능가합니다.이 방법은 또한 평면 [9]그래프를 위해 평면 임베딩(그림)을 효율적으로 계산할 수 있도록 확장되었다.1999년, Shih와 Hsu는 PC 트리(PQ 트리의 루트가 없는 변형)와 [10]정점의 깊이 우선 검색 트리의 후순 트래버설을 사용하여 이러한 방법을 단순화했다.

엣지 덧셈법

2004년 John Boyer와 Wendy Myrvold는[11] PQ 트리 메서드에서 영감을 얻어 심플화된 O(n) 알고리즘을 개발했습니다.이 알고리즘은 PQ 트리를 제거하고 가능하면 평면 임베딩을 계산하기 위해 엣지 추가를 사용합니다.그렇지 않으면 Kuratowski5 하위분할(K 또는3,3 K 중 하나)이 계산된다.이는 현재 두 가지 최신 알고리즘 중 하나입니다(다른 하나는 de Fraysseix, de Mendez 및 Rosenstiehl의[12][13] 평탄도 테스트 알고리즘).Boyer 및 Myrvold 평탄도 테스트의 예비 버전과의 실험적인 비교에 대해서는, 을 참조해 주세요.또한, Boyer-Myrvold 테스트는 [15]출력 크기에 따라 선형적으로 실행되는 실행 시간에 비평면 입력 그래프의 여러 Kuratowski 세분화를 추출하도록 확장되었다.평탄도[16][17] 테스트와 복수의 쿠라토스키 구획의[16] 추출을 위한 소스코드는 공개적으로 이용할 수 있다.꼭지점에서 선형 시간 내에 쿠라토스키 하위 그래프를 찾는 알고리즘은 1980년대에 [18]윌리엄슨에 의해 개발되었다.

시공순서법

다른 방법은 3연결 그래프의 유도 구조를 사용하여 G의 모든 3연결 구성요소의 평면 임베딩을 점진적으로 구축한다(따라서 G [19]자체의 평면 임베딩).시공은 K로 시작하여4 전체 구성요소로 가는 모든 중간 그래프가 다시 3으로 연결되도록 정의됩니다.이러한 그래프는 고유한 임베딩(플라이핑 및 외부 면 선택까지)이 있기 때문에 평면적이더라도 다음 큰 그래프는 이전 그래프를 개선해야 한다.이를 통해 평탄도 테스트를 각 스텝에 대한 테스트로 줄일 수 있습니다.다음으로 추가된 가장자리가 현재 내장되어 있는 외부 면에 양끝이 있는지 여부입니다.이것은 개념적으로 매우 간단하지만(그리고 선형 실행 시간을 제공하지만), 방법 자체는 구성 시퀀스를 찾는 복잡성에 시달립니다.

레퍼런스

  1. ^ 를 클릭합니다Hopcroft, John; Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, doi:10.1145/321850.321852, hdl:1813/6011, S2CID 6279825.
  2. ^ Mehlhorn, Kurt; Mutzel, Petra (1996), "On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm", Algorithmica, 16 (2): 233–242, doi:10.1007/bf01940648, hdl:11858/00-001M-0000-0014-B51D-B, S2CID 10014462
  3. ^ Mehlhorn, Kurt; Mutzel, Petra; Näher, Stefan (1993), An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm
  4. ^ Mehlhorn, Kurt; Näher, Stefan (1995), "LEDA: A library of efficient data types and algorithms", Communications of the ACM, 38 (1): 96–102, CiteSeerX 10.1.1.54.9556, doi:10.1145/204865.204889, S2CID 2560175
  5. ^ Taylor, Martyn G. (2012). Planarity Testing by Path Addition (Ph.D.). University of Kent. Archived from the original on 2016-03-05. Alt URL
  6. ^ 를 클릭합니다Lempel, A.; Even, S.; Cederbaum, I. (1967), "An algorithm for planarity testing of graphs", in Rosenstiehl, P. (ed.), Theory of Graphs, New York: Gordon and Breach, pp. 215–232.
  7. ^ 를 클릭합니다Even, Shimon; Tarjan, Robert E. (1976), "Computing an st-numbering", Theoretical Computer Science, 2 (3): 339–344, doi:10.1016/0304-3975(76)90086-4.
  8. ^ Boyer & Myrvold (2004년), 페이지 243: "LEDA에서의 구현은 다른 많은 O(n) 타임플랜티 알고리즘의 LEDA 구현보다 느립니다."
  9. ^ 를 클릭합니다Chiba, N.; Nishizeki, T.; Abe, A.; Ozawa, T. (1985), "A linear algorithm for embedding planar graphs using PQ–trees", Journal of Computer and System Sciences, 30 (1): 54–76, doi:10.1016/0022-0000(85)90004-2.
  10. ^ 를 클릭합니다Shih, W. K.; Hsu, W. L. (1999), "A new planarity test", Theoretical Computer Science, 223 (1–2): 179–191, doi:10.1016/S0304-3975(98)00120-0.
  11. ^ 를 클릭합니다Boyer, John M.; Myrvold, Wendy J. (2004), "On the cutting edge: simplified O(n) planarity by edge addition" (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273, doi:10.7155/jgaa.00091.
  12. ^ 를 클릭합니다de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1030, arXiv:math/0610935, Bibcode:2006math.....10935D, doi:10.1142/S0129054106004248, S2CID 40107560.
  13. ^ 를 클릭합니다Brandes, Ulrik (2009), The left-right planarity test (PDF).
  14. ^ Boyer, John M.; Cortese, P. F.; Patrignani, M.; Battista, G. D. (2003), "Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm", Proc. 11th Int. Symp. Graph Drawing (GD '03), Lecture Notes in Computer Science, vol. 2912, Springer-Verlag, pp. 25–36
  15. ^ 를 클릭합니다Chimani, M.; Mutzel, P.; Schmidt, J. M. (2008), "Efficient extraction of multiple Kuratowski subdivisions", Proc. 15th Int. Symp. Graph Drawing (GD'07), Lecture Notes in Computer Science, vol. 4875, Sydney, Australia: Springer-Verlag, pp. 159–170.
  16. ^ a b "OGDF - Open Graph Drawing Framework: Start".
  17. ^ "Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0".
  18. ^ Williamson, S. G. (1984), "Depth First Search and Kuratowski Subgraphs", Journal of the ACM, 31 (4): 681–693, doi:10.1145/1634.322451, S2CID 8348222
  19. ^ Schmidt, Jens M. (2014), "The Mondshein Sequence", Automata, Languages, and Programming; Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), Lecture Notes in Computer Science, vol. 8572, pp. 967–978, doi:10.1007/978-3-662-43948-7_80, ISBN 978-3-662-43947-0