내용
-
SPQR tree를 사용하면 그래프의 모든 2-vertex cut을 characterize할 수 있음
-
Block-cut tree가 그래프의 모든 cut vertex를 characterize하고, 그래프를 2-connected component로 나누는 것 처럼 SPQR tree는 그래프의 모든 2-vertex cut을 characterizze하고, 그래프를 3-connected component로 나눌 수 있음
-
이와 별개로 그래프의 triconnectivity를 near-linear하게 판별하는 건 간단한 편
-
SPQR tree의 base case는
- Q. 간선 1개
- R. triconnected graph
-
recursion case는
- S. Series: sub-SPQR tree들을 간선으로 대체하면 사이클이 됨
- P. Parallel: sub-SPQR tree들을 간선으로 대체하면 두 점을 잇는 중복 간선들이 됨
- (사이클이 직선이 아니라는 것 외에는 series parallel graph의 정의와 유사)
-
SPQR tree 자체는 linear하게 build할 수 있고, incremental setting 에서도 near-linear하게 작동할 수 있음
-
decremental setting에서도 되는데, planar-graph라는 precondition이 붙음 https://hal.inria.fr/hal-01925961/document
-
여기서 내릴 수 있는 가장 쉬운 결론은, near-linear time에 incremental하게 2-vertex cut을 관리할 수 있는 자료구조가 존재한다는 것.
-
(참고로, offline setting에서는 near-linear time에 k-connectivity를 관리할 수 있기는 함. https://arxiv.org/abs/1910.10359)
-
.. 여기까지가 SPQR tree를 connectivity라는 관점에서 본 결과인데, 실제로 SPQR tree 자체의 진가는 planar graph와 연결되었을 때 나온다.
-
planar graph와 triconnectivity가 관련이 있는 이유는, 3-connected planar graph에서는 embedding이 unique (up to reflection) 하기 때문.
-
고로 SPQR tree는 planar graph의 모든 가능한 embedding을 표현하는 자료구조로 해석할 수 있다.
-
이걸로 두 문제를 풀 수 있는데
- indegree 0인 유일한 정점 s, outdegree 0인 유일한 정점 t가 같은 face에 속하는 directed planar graph를 planar s-t graph라고 함. 여기서는 DFS preorder/postorder를 가지고 O(1) 에 reachability를 판별할 수 있음이 잘 알려져 있음.
- planar graph에서 edge update가 있을 때 MST 관리
-
결론부터 말하면 이 두 문제를 모두 incremental setting에서 O(log n) 에 해결 가능.
-
개략적으론 이런 식이라고 함. 이 두 문제는 만약에 Embedding이 고정되어 있고 추가되는 간선의 양 끝점이 같은 face에 있는 경우 쉽게 해결을 할 수 있는데, SPQR tree를 사용하면 이 조건이 없어도 똑같은 조건에 해결할 수 있음.
-
원저는 못 구했고 Extended Abstract라서 이에 대한 설명이 없음. 내 추측은 이런 식일 것 같은데, 추가되는 간선의 양 끝점이 같은 face에 없다면 SPQR tree를 그렇게 되도록 rotate해서 (BST처럼 사용) 같은 face에 있도록 하거나 아니면 그것이 절대 불가능함을 보임. 그렇게 되면 두 문제에서 요구하는 조건이 충족되어서 해결 가능
-
결국 이 라인에서 얻어갈 수 있는 점은, SPQR tree는 planar graph의 모든 가능한 embedding을 표현하는 자료구조로 해석할 수 있다 → SPQR tree를 planar graph의 어떤 embedding을 보존하는 자료 구조로 해석할 수 있다 로 볼 수 있는 것이고
-
이렇게 되면 결국 embedding이라는 것을 트리의 형태로 표현할 수 있는 방법을 얻게 됨
-
https://arxiv.org/pdf/1911.03449.pdf 그래서 fully-dynamic planarity 문제에서도 SPQR tree가 주는 representation을 활용
출처: https://koosaga.com/288 [구사과:티스토리]