평면 그래프의 면 찾기¶
$n$개의 정점과 $m$개의 간선을 가진 그래프 $G$를 생각해 봅시다. 이 그래프는 두 간선이 공통 정점(존재하는 경우)에서만 교차하도록 평면 위에 그릴 수 있습니다. 이러한 그래프를 평면 그래프라고 합니다. 이제 평면 그래프와 함께 그 직선 임베딩이 주어진다고 가정합시다. 이는 각 정점 $v$마다 대응하는 점 $(x, y)$가 있고, 모든 간선이 이 점들 사이의 선분으로 서로 교차하지 않게 그려진다는 뜻입니다(이러한 임베딩은 항상 존재합니다). 이 선분들은 평면을 여러 영역으로 나누며, 이 영역들을 면이라고 합니다. 면 중 정확히 하나는 유계가 아닙니다. 이 면을 외부 면이라고 하고, 나머지 면들을 내부 면이라고 합니다.
이 글에서는 평면 그래프의 내부 면과 외부 면을 모두 찾는 방법을 다룹니다. 그래프는 연결되어 있다고 가정합니다.
평면 그래프에 관한 몇 가지 사실¶
이 절에서는 평면 그래프에 관한 몇 가지 사실을 증명 없이 제시합니다. 증명에 관심이 있는 독자는 Graph Theory by R. Diestel(이 책을 바탕으로 한 평면성에 관한 영상 강의도 참고하십시오)이나 다른 책을 참고하십시오.
오일러 정리¶
오일러 정리에 따르면 $n$개의 정점, $m$개의 간선, $f$개의 면을 가진 연결 평면 그래프의 모든 올바른 임베딩은 다음을 만족합니다:
더 일반적으로, $k$개의 연결 요소를 가진 모든 평면 그래프는 다음을 만족합니다:
평면 그래프의 간선 수.¶
$n \ge 3$이면 $n$개의 정점을 가진 평면 그래프의 최대 간선 수는 $3n - 6$입니다. 이 수는 모든 면이 삼각형으로 둘러싸인 연결 평면 그래프라면 어떤 것에서든 달성됩니다. 복잡도 측면에서 이 사실은 모든 평면 그래프에 대해 $m = O(n)$임을 의미합니다.
평면 그래프의 면 수.¶
위 사실의 직접적인 결과로, $n \ge 3$이면 $n$개의 정점을 가진 평면 그래프의 최대 면 수는 $2n - 4$입니다.
평면 그래프의 최소 정점 차수.¶
모든 평면 그래프에는 차수가 5 이하인 정점이 존재합니다.
알고리즘¶
먼저 각 정점에 인접한 간선들을 편각 기준으로 정렬합니다. 이제 다음과 같은 방식으로 그래프를 순회합시다. 간선 $(v, u)$를 통해 정점 $u$에 들어왔고, $u$의 정렬된 인접 리스트에서 $(v, u)$ 다음 간선이 $(u, w)$라고 가정합시다. 그러면 다음 정점은 $w$가 됩니다. 어떤 간선 $(v, u)$에서 이 순회를 시작하면 $(v, u)$에 인접한 면 중 정확히 하나를 순회하게 된다는 사실이 밝혀지며, 어느 면을 순회하는지는 첫 단계가 $u$에서 $v$로 가는지 $v$에서 $u$로 가는지에 따라 달라집니다.
이제 알고리즘은 꽤 명확합니다. 그래프의 모든 간선을 순회하면서, 이전 순회 중 어느 것에서도 방문되지 않은 각 간선에 대해 순회를 시작해야 합니다. 이렇게 하면 각 면을 정확히 한 번씩 찾게 되며, 각 간선은 두 번(각 방향으로 한 번씩) 순회됩니다.
다음 간선 찾기¶
순회하는 동안 반시계 방향 순서로 다음 간선을 찾아야 합니다. 다음 간선을 찾는 가장 직관적인 방법은 각도를 기준으로 한 이진 탐색입니다. 그러나 각 정점에 인접한 간선들의 반시계 방향 순서가 주어진다면, 다음 간선들을 미리 계산하여 해시 테이블에 저장할 수 있습니다. 간선들이 이미 각도순으로 정렬되어 있다면, 이 경우 모든 면을 찾는 복잡도는 선형이 됩니다.
외부 면 찾기¶
이 알고리즘이 각 내부 면은 시계 방향으로, 외부 면은 반시계 방향으로 순회한다는 것을 어렵지 않게 알 수 있으므로, 각 면의 순서를 확인하여 외부 면을 찾을 수 있습니다.
복잡도¶
정렬 때문에 알고리즘의 복잡도가 $O(m \log m)$이라는 것은 꽤 명확하며, $m = O(n)$이므로 실제로는 $O(n \log n)$입니다. 앞서 언급했듯이, 정렬이 없으면 복잡도는 $O(n)$이 됩니다.
그래프가 연결되어 있지 않다면 어떻게 됩니까?¶
언뜻 보기에는 각 연결 요소에 대해 같은 알고리즘을 실행하면 되므로, 연결되지 않은 그래프의 면을 찾는 것이 그리 어렵지 않아 보일 수 있습니다. 그러나 연결 요소들이 중첩된 방식으로 그려져 구멍을 형성할 수 있습니다(아래 그림 참고). 이 경우 어떤 연결 요소의 내부 면이 다른 몇몇 연결 요소의 외부 면이 되며, 복잡하고 연결되지 않은 경계를 갖게 됩니다. 이러한 경우를 다루는 것은 꽤 어려우며, 한 가지 가능한 접근법은 점 위치 알고리즘으로 중첩된 연결 요소를 식별하는 것입니다.
구현¶
다음 구현은 각 면에 대해 정점들의 벡터를 반환하며, 외부 면이 가장 먼저 옵니다. 내부 면들은 반시계 방향 순서로 반환되고 외부 면은 시계 방향 순서로 반환됩니다.
간단하게 하기 위해 각도를 기준으로 이진 탐색을 수행하여 다음 간선을 찾습니다.
struct Point {
int64_t x, y;
Point(int64_t x_, int64_t y_): x(x_), y(y_) {}
Point operator - (const Point & p) const {
return Point(x - p.x, y - p.y);
}
int64_t cross (const Point & p) const {
return x * p.y - y * p.x;
}
int64_t cross (const Point & p, const Point & q) const {
return (p - *this).cross(q - *this);
}
int half () const {
return int(y < 0 || (y == 0 && x < 0));
}
};
std::vector<std::vector<size_t>> find_faces(std::vector<Point> vertices, std::vector<std::vector<size_t>> adj) {
size_t n = vertices.size();
std::vector<std::vector<char>> used(n);
for (size_t i = 0; i < n; i++) {
used[i].resize(adj[i].size());
used[i].assign(adj[i].size(), 0);
auto compare = [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[i];
Point pr = vertices[r] - vertices[i];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
};
std::sort(adj[i].begin(), adj[i].end(), compare);
}
std::vector<std::vector<size_t>> faces;
for (size_t i = 0; i < n; i++) {
for (size_t edge_id = 0; edge_id < adj[i].size(); edge_id++) {
if (used[i][edge_id]) {
continue;
}
std::vector<size_t> face;
size_t v = i;
size_t e = edge_id;
while (!used[v][e]) {
used[v][e] = true;
face.push_back(v);
size_t u = adj[v][e];
size_t e1 = std::lower_bound(adj[u].begin(), adj[u].end(), v, [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[u];
Point pr = vertices[r] - vertices[u];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
}) - adj[u].begin() + 1;
if (e1 == adj[u].size()) {
e1 = 0;
}
v = u;
e = e1;
}
std::reverse(face.begin(), face.end());
Point p1 = vertices[face[0]];
__int128 sum = 0;
for (int j = 0; j < face.size(); ++j) {
Point p2 = vertices[face[j]];
Point p3 = vertices[face[(j + 1) % face.size()]];
sum += (p2 - p1).cross(p3 - p2);
}
if (sum <= 0) {
faces.insert(faces.begin(), face);
} else {
faces.emplace_back(face);
}
}
}
return faces;
}
선분들로부터 평면 그래프 만들기¶
그래프가 명시적으로 주어지지 않고 평면 위의 선분 집합으로 주어지는 경우가 있으며, 이때 실제 그래프는 아래 그림과 같이 그 선분들이 서로 교차하여 만들어집니다. 이 경우에는 그래프를 직접 구성해야 합니다. 가장 쉬운 방법은 다음과 같습니다. 선분 하나를 고정하고 그 선분과 다른 모든 선분의 교점을 구합니다. 그런 다음 모든 교점을 해당 선분의 두 끝점과 함께 사전순으로 정렬하고, 이들을 정점으로 그래프에 추가합니다. 또한 사전순으로 인접한 두 정점끼리 간선으로 연결합니다. 모든 간선에 대해 이 과정을 수행하고 나면 그래프를 얻게 됩니다. 물론 서로 같은 두 교점이 항상 같은 정점에 대응하도록 해야 합니다. 이를 위한 가장 쉬운 방법은 점들을 좌표를 기준으로 map에 저장하되, 좌표 차이가 작은 수(예를 들어 $10^{-9}$ 미만)인 점들을 같은 점으로 간주하는 것입니다. 이 알고리즘은 $O(n^2 \log n)$에 동작합니다.
구현¶
using dbl = long double;
const dbl eps = 1e-9;
struct Point {
dbl x, y;
Point(){}
Point(dbl x_, dbl y_): x(x_), y(y_) {}
Point operator * (dbl d) const {
return Point(x * d, y * d);
}
Point operator + (const Point & p) const {
return Point(x + p.x, y + p.y);
}
Point operator - (const Point & p) const {
return Point(x - p.x, y - p.y);
}
dbl cross (const Point & p) const {
return x * p.y - y * p.x;
}
dbl cross (const Point & p, const Point & q) const {
return (p - *this).cross(q - *this);
}
dbl dot (const Point & p) const {
return x * p.x + y * p.y;
}
dbl dot (const Point & p, const Point & q) const {
return (p - *this).dot(q - *this);
}
bool operator < (const Point & p) const {
if (fabs(x - p.x) < eps) {
if (fabs(y - p.y) < eps) {
return false;
} else {
return y < p.y;
}
} else {
return x < p.x;
}
}
bool operator == (const Point & p) const {
return fabs(x - p.x) < eps && fabs(y - p.y) < eps;
}
bool operator >= (const Point & p) const {
return !(*this < p);
}
};
struct Line{
Point p[2];
Line(Point l, Point r){p[0] = l; p[1] = r;}
Point& operator [](const int & i){return p[i];}
const Point& operator[](const int & i)const{return p[i];}
Line(const Line & l){
p[0] = l.p[0]; p[1] = l.p[1];
}
Point getOrth()const{
return Point(p[1].y - p[0].y, p[0].x - p[1].x);
}
bool hasPointLine(const Point & t)const{
return std::fabs(p[0].cross(p[1], t)) < eps;
}
bool hasPointSeg(const Point & t)const{
return hasPointLine(t) && t.dot(p[0], p[1]) < eps;
}
};
std::vector<Point> interLineLine(Line l1, Line l2){
if(std::fabs(l1.getOrth().cross(l2.getOrth())) < eps){
if(l1.hasPointLine(l2[0]))return {l1[0], l1[1]};
else return {};
}
Point u = l2[1] - l2[0];
Point v = l1[1] - l1[0];
dbl s = u.cross(l2[0] - l1[0])/u.cross(v);
return {Point(l1[0] + v * s)};
}
std::vector<Point> interSegSeg(Line l1, Line l2){
if (l1[0] == l1[1]) {
if (l2[0] == l2[1]) {
if (l1[0] == l2[0])
return {l1[0]};
else
return {};
} else {
if (l2.hasPointSeg(l1[0]))
return {l1[0]};
else
return {};
}
}
if (l2[0] == l2[1]) {
if (l1.hasPointSeg(l2[0]))
return {l2[0]};
else
return {};
}
auto li = interLineLine(l1, l2);
if (li.empty())
return li;
if (li.size() == 2) {
if (l1[0] >= l1[1])
std::swap(l1[0], l1[1]);
if (l2[0] >= l2[1])
std::swap(l2[0], l2[1]);
std::vector<Point> res(2);
if (l1[0] < l2[0])
res[0] = l2[0];
else
res[0] = l1[0];
if (l1[1] < l2[1])
res[1] = l1[1];
else
res[1] = l2[1];
if (res[0] == res[1])
res.pop_back();
if (res.size() == 2u && res[1] < res[0])
return {};
else
return res;
}
Point cand = li[0];
if (l1.hasPointSeg(cand) && l2.hasPointSeg(cand))
return {cand};
else
return {};
}
std::pair<std::vector<Point>, std::vector<std::vector<size_t>>> build_graph(std::vector<Line> segments) {
std::vector<Point> p;
std::vector<std::vector<size_t>> adj;
std::map<std::pair<int64_t, int64_t>, size_t> point_id;
auto get_point_id = [&](Point pt) {
auto repr = std::make_pair(
int64_t(std::round(pt.x * 1000000000) + 1e-6),
int64_t(std::round(pt.y * 1000000000) + 1e-6)
);
if (!point_id.count(repr)) {
adj.emplace_back();
size_t id = point_id.size();
point_id[repr] = id;
p.push_back(pt);
return id;
} else {
return point_id[repr];
}
};
for (size_t i = 0; i < segments.size(); i++) {
std::vector<size_t> curr = {
get_point_id(segments[i][0]),
get_point_id(segments[i][1])
};
for (size_t j = 0; j < segments.size(); j++) {
if (i == j)
continue;
auto inter = interSegSeg(segments[i], segments[j]);
for (auto pt: inter) {
curr.push_back(get_point_id(pt));
}
}
std::sort(curr.begin(), curr.end(), [&](size_t l, size_t r) { return p[l] < p[r]; });
curr.erase(std::unique(curr.begin(), curr.end()), curr.end());
for (size_t j = 0; j + 1 < curr.size(); j++) {
adj[curr[j]].push_back(curr[j + 1]);
adj[curr[j + 1]].push_back(curr[j]);
}
}
for (size_t i = 0; i < adj.size(); i++) {
std::sort(adj[i].begin(), adj[i].end());
// removing edges that were added multiple times
adj[i].erase(std::unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
return {p, adj};
}