Dual of Planar Graph

Dual of Planar Graph, 평면 그래프의 쌍대, Planar Dual

정의

평면 그래프 (planar graph) G 의 쌍대 그래프 (dual graph) G* 는 G 의 각 면 (face) 을 정점으로, G 의 두 면을 공유하는 각 간선을 G* 의 간선으로 만든 그래프.

쌍대로 가면 min-cut 이 shortest path 가 되는 마법 이 일어난다 (max-flow min-cut + planar duality). PS 에서는 평면 그래프에서의 흐름 / 컷 문제를 다익스트라로 변환 하는 핵심 도구.

문제 상황과 동기

평면 그래프에서 s-t min-cut 을 구하고 싶다. 일반 그래프는 Dinic / Push-Relabel 로 O(V² E) ~ O(V³). 하지만 평면 그래프는 dual graph 의 s*-t* shortest path 로 변환 가능하다.

naive min-cut: O(V² E)
dual + Dijkstra: O((V+E) log V)

핵심 통찰: 평면 그래프의 cycle ↔ dual cut, cut ↔ dual cycle. s, t 를 가르는 cut 은 dual 에서 s*, t* 를 잇는 경로에 대응. 각 간선의 용량을 dual 간선의 거리로 두면 shortest path = min-cut.

PS 에서는 Masonry Bridge (다리 교차 문제), 평면 영역 게임, 면 합치기 같은 문제에 등장. Push-Relabel, Cost Scaling 대신 Dijkstra 로 해결 가능해 코드가 훨씬 짧다.

핵심 성질

1. |V*| = F (외부 면 포함)
2. |E*| = |E|
3. G 의 cycle ↔ G* 의 cut, G 의 cut ↔ G* 의 cycle
4. s-t min-cut in planar G ↔ s*-t* shortest path in G*
5. MST in G ↔ Max-weight spanning tree complement in G*

시각화

min-cut → shortest path 변환

s, t 가 외부 면 위에 있도록 정점 위치를 잡고 (필요시 외부 면 변경), s 와 t 사이에 가상 간선 추가. 이 가상 간선이 면을 두 영역으로 가른다. 두 영역의 dual 정점을 s*, t* 라 하면:

min-cut(s, t in G) = shortest-path(s*, t* in G*)

따라서 O(V² log V) 가 아닌 O((V+E) log V) 다익스트라 로 min-cut.

작은 예시

평면 그래프:
    s ---2--- a ---3--- t
    |         |         |
    1         1         1
    |         |         |
    b ---2--- c ---2--- d

면 (face):
  f1: 외부 면 (s, a, t, d, c, b 둘러싸고)
  f2: s-a-c-b 내부
  f3: a-t-d-c 내부

dual 그래프 G*:
  정점: f1, f2, f3
  간선:
    f1-f2 (s-b, s-a 공유) 용량 = min(1, 2)
    f2-f3 (a-c, b-c 공유) 용량 = min(1, 2)
    f1-f3 (a-t, t-d, d-c 공유) 용량 = min(3, 1, 2)

s-t 가상 간선 추가 → f1 을 f1_left, f1_right 로 분할
  s* = f1_left, t* = f1_right

shortest path (s*, t*) in G* = min-cut (s, t) in G

면 구성 (faces) 어떻게 찾는가

각 간선을 양 방향 half-edge 로 두고, 각 정점에서 들어오는 half-edge 를 각도순 정렬 한다. half-edge (u, v) 의 다음 face 진행은 v 에서 (v, u) 의 이전 half-edge.

for each half-edge h:
    follow h -> next -> next -> ... until 되돌아옴
    이 시퀀스가 한 면의 경계

각도 정렬은 좌표가 있으면 atan2, 좌표가 없으면 별도 임베딩 정보 필요.

Pseudocode (Half-edge traversal)

find_faces(G with coordinates):
  for each vertex v:
    sort outgoing edges by angle (atan2)
  
  visited_half_edges = {}
  faces = []
  
  for each directed edge (u, v):
    if (u, v) in visited_half_edges: continue
    
    face = []
    current = (u, v)
    while current not in visited_half_edges:
      visited_half_edges.add(current)
      face.append(current)
      
      // next half-edge: v 에서 (v, u) 의 ccw 다음
      next_v = current.to
      next_u = next outgoing edge from next_v after (next_v, current.from)
      current = (next_v, next_u)
    
    faces.append(face)
  
  return faces

응용

1. Masonry Bridge 류

다리들 사이로 차량/사람이 지나는 최대 흐름 → 평면 쌍대로 변환 후 다익스트라.

2. 평면 그래프 게임

평면 그래프의 영역을 차지하는 게임, dual 위 그래프 게임으로 변환.

3. 면 합치기 / 영역 카운팅

dual 위에서 union-find.

구현

Dual graph 구성 + s-t shortest path

// O((V+E) log V), 평면 그래프의 s-t min-cut
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

struct Edge { int to; double cap; };

// 좌표 기반 dual graph 구성 (pseudocode)
// 실제 구현은 half-edge + face traversal 필요
// 여기서는 dual + Dijkstra 부분만 제시

double planar_min_cut(int n, int s, int t,
                      const vector<vector<Edge>>& dual_graph,
                      int s_star, int t_star) {
    // dual_graph: 이미 면 기반 dual 로 구성됨
    // s_star, t_star: s, t 를 가르는 두 면의 dual 정점
    
    vector<double> dist(dual_graph.size(), 1e18);
    priority_queue<pair<double, int>> pq;
    dist[s_star] = 0;
    pq.push({0, s_star});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;
        if (d > dist[u]) continue;
        
        for (auto& e : dual_graph[u]) {
            if (dist[e.to] > dist[u] + e.cap) {
                dist[e.to] = dist[u] + e.cap;
                pq.push({-dist[e.to], e.to});
            }
        }
    }
    
    return dist[t_star];
}

// 실전: 좌표 기반 face 구성은 atan2 + half-edge sorting
// 또는 combinatorial embedding 정보 활용

실무에서는 CGAL, Boost.Graph 같은 라이브러리 사용. PS 에서는 문제마다 평면 임베딩이 주어지는 경우가 많아 직접 구현.

함정

1. 평면성 확인

문제에서 평면 그래프가 보장된 경우에만 사용. 일반 그래프는 적용 불가.

2. 외부 면 처리

외부 면을 명시적으로 정점화. 빠뜨리면 dual 정점 수가 F-1.

3. 좌표 정확도

각도 정렬 시 부동소수점 오차로 면 구성이 깨질 수 있다. 가능하면 정수 좌표 cross product 비교.

4. multi-edge / self-loop

같은 두 면을 공유하는 두 간선은 dual 에서 multi-edge. self-loop 는 면 안에 매달린 형태. 케이스 처리.

구현 팁

1. 좌표 정렬: atan2(y, x) 대신 cross product 로 각도 비교하면 정수 연산 가능
2. 외부 면 식별: 가장 큰 면적 또는 무한대 좌표 포함 면
3. s, t 위치: 외부 면에 없으면 가상 간선 추가로 외부 면 분할

BOJ 연습 문제

번호	제목	링크
BOJ 13145	Masonry Bridge	kokoa-lab
BOJ 17442	삼분 그래프	kokoa-lab
BOJ 15308	비밀 요원	kokoa-lab
BOJ 18941	평면그래프와 게임	kokoa-lab

참고

• Push-Relabel / Cost Scaling
• Voronoi Diagram
• Bulldozer Trick