이분할 평면 그래프의 격자 표현을 위한 선형시간 알고리즘
박승배, 임형석 · 정보과학회논문지(A) · 1996
평면상에 주어진 서로 겹쳐 있지 않은 수직선분들과 수평선분들의 집합 S에 대하여, 선분을 정점으로 대응시키고 두 선분이 교차하면 해당되는 두 정점사이에 에지를 둔 그래프 G를 S에 대한 격자 교차 그래프라고 한다. 그리고 S를 G에 대한 격자 표현이라 한다. 모든 격자 교차 그래프는 이분할 그래프이나 그 역은 성립하지 않는다. 그동안 격자 교차 그래프인 이 분할 그래프들과 격자 교차 그래프가 아닌 이분할 그래프들에 대한 연구가 진행되어져 왔다. 그리고 주어진 그래프 G와 양의 정수 M, N에 대하여 M^*N 격자 구조에 G의 격자 표현을 나타낼 수 있는가 하는 문제는 NP-complete 임이 밝혀져 있다. 본 논문에서는 격자 교차 그래프의 한 부류로 알려진 이분할 평면 그래프 G(W, B:E)의 격자 표현을 ㅣWㅣ^*ㅣBㅣ격자 구조에 구하는 선형시간 알고리즘과 이분할 비평면 그래프가 격자 교차 그래프이기 위한 새로운 필요조건을 제시한다.
Cited by 0 works.