평면 그래프 (Planar Graph)

정의

평면 그래프 (Planar Graph) 는 간선끼리 교차하지 않고 평면에 그릴 수 있는 그래프. 연결된 평면 그래프는 항상 Euler 공식 V - E + F = 2 를 만족한다, 여기서 V = 꼭짓점, E = 간선, F = 면(face). 평면 그래프의 대표적인 비존재 정리로 Kuratowski 정리: 그래프가 평면 iff K_5 또는 K_{3,3} 을 세부 그래프로 포함하지 않는다.

문제 상황과 동기

회로 기판(PCB) 배선, 지도 색칠(4색 정리), VLSI 설계 등에서 간선 교차를 허용할 수 없는 상황. 컴퓨터 비전의 planar SLAM, 그래프 마이닝의 genus 계산까지 확장됨. Naive planar embedding 은 NP-hard 이지만, 평면성 검사는 O(V+E) 에 가능 (Hopcroft-Tarjan).

핵심 통찰: 면(faces)까지 포함한 combinatorial count가 V, E 만으로 결정된다 는 Euler 공식이 평면 그래프 이론의 기둥.

시각화

핵심 아이디어

Euler's formula (connected planar graph):
  V - E + F = 2

Necessary condition (V >= 3):
  E <= 3V - 6

Kuratowski's theorem:
  G is planar  <=>  G has no subgraph homeomorphic to K_5 or K_{3,3}

평면 그래프의 면에는 바깥 면(outer face) 도 포함된다. Triangulation (최대 평면 그래프) 은 E = 3V - 6 을 만족.

• Euler 지표: V - E + F = 2(C - G) 로 일반화 (C = 연결 성분 수, G = genus)
• K_5: 5개의 꼭짓점이 모두 연결 (K_5 = 10 간선). 3V-6 = 9 이므로 평면 불가.
• K_{3,3}: 3+3 완전 이분 그래프 (9 간선). E = 9 > 3V-6 = 12(v=6), 필연 조건은 통과하지만 non-planar (Kuratowski).

알고리즘

planarity_test(V, E, adj):
  if V < 3: return true
  if E > 3V - 6: return false          # necessary condition
  # Hopcroft-Tarjan O(V+E) planarity test
  # DFS-free numbering + lowlink 로 embedding 시도
  # 세부 Kuratowski subgraph 탐지
  return planarity_embedding(V, adj)   # 성공시 true

구현

// Planar graph necessary condition + Euler formula verification
#include <bits/stdc++.h>
using namespace std;
int main() {
  int v, e; cin >> v >> e;
  vector<vector<int>> adj(v);
  for (int i = 0; i < e; i++) {
      int a, b; cin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
  }
  // Necessary condition: E <= 3V - 6 (for V >= 3)
  if (v >= 3 && e > 3 * v - 6) {
      cout << "NOT PLANAR (E > 3V-6: " << e << " > " << 3*v-6 << ")\n";
      return 0;
  }
  // Euler test: given face count F
  int f; cin >> f;
  if (v - e + f == 2) {
      cout << "Euler formula holds: V-E+F = " << v << "-" << e << "+" << f << " = 2\n";
      cout << "PLANAR (consistent with planar embedding)\n";
  } else {
      cout << "Euler formula fails: V-E+F = " << v-e+f << " != 2\n";
  }
  return 0;
}

def main():
  v, e = map(int, input().split())
  adj = [[] for _ in range(v)]
  for _ in range(e):
      a, b = map(int, input().split())
      adj[a].append(b); adj[b].append(a)
  if v >= 3 and e > 3 * v - 6:
      print("NOT PLANAR (E > 3V-6)")
      return
  f = int(input())
  if v - e + f == 2:
      print(f"Euler holds: {v}-{e}+{f}=2")
      print("PLANAR")
  else:
      print(f"Euler fails: {v}-{e}+{f} != 2")
​
if __name__ == "__main__":
  main()

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int v = Integer.parseInt(st.nextToken());
      int e = Integer.parseInt(st.nextToken());
      ArrayList<Integer>[] adj = new ArrayList[v];
      for (int i = 0; i < v; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < e; i++) {
          st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          adj[a].add(b); adj[b].add(a);
      }
      if (v >= 3 && e > 3 * v - 6) {
          System.out.println("NOT PLANAR (E > 3V-6)");
          return;
      }
      int f = Integer.parseInt(br.readLine());
      if (v - e + f == 2)
          System.out.println("Euler holds: " + v + "-" + e + "+" + f + "=2\nPLANAR");
      else
          System.out.println("Euler fails: " + (v - e + f) + " != 2");
  }
}

4 6
0 1
0 2
0 3
1 2
1 3
2 3
4

Euler holds: 4-6+4=2
PLANAR

5 10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
7

NOT PLANAR (E > 3V-6: 10 > 9)

복잡도

변형 / 활용

응용: PCB / VLSI routing (간선 교차 금지), 지도 제작 (4색 정리), 네트워크 다이어그램, Feynman diagram.

함정

1. 필요 조건 vs 충분 조건

E <= 3V - 6 은 필요 조건일 뿐 충분하지 않음. K_{3,3} 은 V=6, E=9 <= 12 이지만 planar 가 아님.

2. 면의 정의

바깥 면(outer face) 도 면의 개수에 포함. Disconnected graph 는 V - E + F = 1 + C (C=연결성분).

3. K_4 는 planar, K_5 는 non-planar

K_4 (V=4, E=6, F=4) 는 Euler 를 만족하고 평면에 교차 없이 그릴 수 있음. K_5 (V=5, E=10) 는 간선이 하나 비껴서 교차가 불가피.

BOJ 연습 문제

참고

• 볼록 껍질
• 볼록 다각형 점 판정