평면 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

평면 그래프는 평면 위에 교차하는 변 없이 그릴 수 있는 그래프를 의미한다. 쿠라토프스키 정리와 바그너 정리에 따르면, K₅(5개의 꼭짓점을 가진 완전 그래프) 또는 K₃,₃(완전 이분 그래프)를 마이너로 갖지 않는 그래프는 평면 그래프이다. 평면 그래프는 오일러 공식을 따르며, 4색 정리에 의해 4가지 색으로 채색될 수 있다. 극대 평면 그래프, 외평면 그래프, 할린 그래프 등 다양한 종류가 있으며, 상향 평면 그래프, 볼록 평면 그래프와 같은 특수한 형태도 존재한다. 평면 그래프는 4색 정리와 같은 중요한 정리의 기반이 되며, 그래프 이론에서 중요한 연구 대상이다.

더 읽어볼만한 페이지

평면 그래프 - 다듬은 정육면체
깎은 정육면체는 정육면체의 꼭짓점을 잘라 만든 다면체로, 6개의 정팔각형과 8개의 정삼각형으로 구성되고, 마름모 입방팔면체 등과 연관되며, 데카르트 좌표계와 트리보나치 수열로 꼭짓점 위치를 나타낼 수 있고, 키랄성 및 팔면체 대칭성을 가지며 여러 분야에 활용됩니다.
평면 그래프 - 정이십면체
정이십면체는 20개의 정삼각형 면으로 이루어진 볼록 정다면체로, 정반오각기둥 양쪽에 정오각뿔을 붙인 형태이며, 정십이면체와 쌍대 관계를 가지고 다양한 분야에서 활용된다.
그래프족 - 척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다.
그래프족 - 정규 그래프
정규 그래프는 그래프 이론에서 모든 꼭짓점의 차수가 동일한 그래프를 의미하며, 각 꼭짓점이 k개의 변에 잇닿아 있는 그래프를 k-정규 그래프라고 하고, 여러 성질 및 다양한 분야에 응용된다.

평면 그래프
개요
평면 그래프의 예시
정의	평면에 교차하지 않게 그릴 수 있는 그래프
관련 개념	그래프 이론 위상 수학
성질
오일러 공식	평면 그래프 G에 대해 v - e + f = k + 1 (v: 정점 수, e: 변 수, f: 면 수, k: 연결 요소 수)
쿠라토프스키 정리	그래프가 평면 그래프일 필요충분조건은 K5 또는 K3,3을 부분 그래프로 포함하지 않는 것이다.
페트르센 그래프	평면 그래프가 아닌 최소 그래프
알고리즘
평면성 테스트	주어진 그래프가 평면 그래프인지 여부를 판단하는 알고리즘
평면 임베딩	평면 그래프를 평면에 교차 없이 그리는 알고리즘
응용
회로 기판 설계	전자 회로를 평면에 배치하는 데 사용
지도 제작	지도를 평면에 표현하는 데 사용
데이터 시각화	복잡한 데이터를 시각적으로 표현하는 데 사용

2. 정의

3. 판별법

3. 1. 쿠라토프스키 정리

카지미에시 쿠라토프스키는 금지된 그래프 특성화를 사용하여 평면 그래프를 특징지었으며, 이는 현재 쿠라토프스키 정리로 알려져 있다.

쿠라토프스키 정리에 따르면, 어떤 임의의 그래프가 평면 그래프일 필요충분조건은 그 그래프에는 K₅(꼭짓점이 5개인 완전 그래프) 또는 K₃,₃(완전 이분 그래프)을 마이너로 갖지 않는다는 것이다. 유한 그래프는 K₅ 완전 그래프 또는 K₃,₃ 완전 이분 그래프(유틸리티 그래프)의 세분인 부분 그래프를 포함하지 않는다면 평면 그래프이다.

그래프의 세분은 모서리에 정점을 삽입한 결과이다(예를 들어, 모서리 • —— •를 • — • — •로 변경).

바그너 정리는 세분 대신 마이너를 다룬다. 유한 그래프는 K₅ 또는 K₃,₃을 마이너로 갖지 않는 경우에 평면 그래프이다. 그래프의 마이너는 부분 그래프를 취하고 모서리를 정점으로 반복적으로 수축하여 생성되며, 원래 끝점의 각 이웃은 새 정점의 이웃이 된다.

페테르센 그래프가 K₃,₃ 그래프와 동형인 마이너를 포함하고 있으므로 비평면 그래프임을 보여주는 애니메이션

클라우스 바그너는 더 일반적으로 그래프의 모든 마이너 닫힌 클래스가 유한한 "금지된 마이너" 집합에 의해 결정되는지 질문했다. 이것은 현재 긴 일련의 논문에서 증명된 로버트슨-세이모어 정리이다. 이 정리의 언어에서, K₅와 K₃,₃은 유한 평면 그래프 클래스의 금지된 마이너이다.

3. 2. 바그너 정리

카지미에시 쿠라토프스키의 정리에 따르면, 어떤 임의의 그래프가 평면 그래프일 필요충분조건은 그 그래프에는 K₅(꼭짓점이 5개인 완전 그래프) 또는 K₃,₃을 마이너로 갖지 않는다는 것이다. 바그너 정리는 세분 대신 마이너를 다룬다.

클라우스 바그너가 제시한 정리로, 쿠라토프스키 정리와 유사하지만 세분 대신 마이너 개념을 사용한다. 유한 그래프는 K₅ 또는 K₃,₃을 마이너로 갖지 않는 경우에 평면 그래프이다. 그래프의 마이너는 부분 그래프를 취하고 모서리를 정점으로 반복적으로 수축하여 생성되며, 원래 끝점의 각 이웃은 새 정점의 이웃이 된다.

3. 3. 기타 판별법

실제로, 주어진 그래프가 평면 그래프인지 빠르게 결정하기 위해 쿠라토프스키의 기준을 사용하는 것은 어렵다. 하지만 이 문제에 대한 빠른 알고리즘이 존재한다. ''n''개의 정점을 가진 그래프의 경우, 그래프가 평면 그래프인지 아닌지를 ''O''(''n'') 시간(선형 시간) 내에 결정할 수 있다(평면성 검사 참조).

''v''개의 정점과 ''e''개의 변, ''f''개의 면을 가진 단순 연결 평면 그래프의 경우, ''v'' ≥ 3에 대해 다음과 같은 간단한 조건이 성립한다.

정리 1. ''e'' ≤ 3''v'' – 6
정리 2. 길이가 3인 사이클이 없으면, ''e'' ≤ 2''v'' – 4.
정리 3. ''f'' ≤ 2''v'' – 4.

이러한 의미에서, 평면 그래프는 희소 그래프이며, 최대 ''O''(''v''²)보다 점근적으로 작은 ''O''(''v'') 개의 변만 갖는다. 예를 들어, 그래프 ''K''_3,3은 6개의 정점, 9개의 변, 길이가 3인 사이클이 없다. 따라서 정리 2에 의해 평면 그래프가 될 수 없다. 이 정리는 평면성이 되기 위한 필요 조건을 제공하지만 충분 조건은 아니므로, 그래프가 평면 그래프가 아니라는 것을 증명하는 데만 사용할 수 있으며 평면 그래프라는 것을 증명할 수는 없다. 정리 1과 2가 모두 실패하면, 다른 방법을 사용할 수 있다.

휘트니의 평면성 기준은 대수적 쌍대성의 존재에 기반한 특징을 제공한다.
맥 레인의 평면성 기준은 사이클 공간을 통해 유한 평면 그래프의 대수적 특징을 제공한다.
프레이세익-로젠스틸 평면성 기준은 깊이 우선 탐색 트리의 공동 트리 변의 이분할 존재에 기반한 특징을 제공한다. 이는 좌-우 평면성 검사 알고리즘의 핵심이다.
슈나이더의 정리는 부분 순서 차원의 측면에서 평면성에 대한 특징을 제공한다.
콜린 드 베르디에의 평면성 기준은 그래프에 의해 정의된 특정 슈뢰딩거 연산자의 두 번째 고유값의 최대 중복도에 기반한 특징을 제공한다.
하나니-튜트 정리는 그래프가 각 독립된 변 쌍이 짝수 번 교차하는 그림을 가지는 경우에만 평면 그래프이며, 이는 2를 법으로 하는 일련의 방정식을 통해 평면 그래프를 특징짓는 데 사용될 수 있다.

4. 성질

평면 그래프는 여러 유용한 성질들을 가지고 있다.

평면 그래프의 오일러 지표는 2이다. 즉, 꼭짓점의 수를 $v$ , 변의 수를 $e$ , 면의 수를 $f$ 라고 하면, 다음 식이 성립한다.

:

v - e + f = 2

:이때 면은 변으로 닫힌 유한한 넓이의 면뿐만 아니라, 무한한 넓이의 면도 포함한다. 예를 들어, 꼭짓점 세 개가 서로 연결된 K₃ 그래프에서 면의 수는 2가 된다. 이는 평면 그래프가 구면 위에서 정의되는데, 구면의 오일러 지표가 2이기 때문이다.

4색정리에 의하면, 평면 그래프에서는 인접한 두 꼭짓점이 다른 색을 갖도록 4개의 색깔로 꼭짓점을 칠할 수 있다.
평면 그래프에는 무한 면이 단 하나 있다.^[21]
G가 단순 그래프이고 평면 그래프라면, G는 차수가 5 이하인 꼭짓점을 갖는다.^[21]
G가 평면 그래프라면, |E(G)|≦3|V(G)|-6이다. (단, |V(G)|≧3)^[21]
G가 평면 이분 그래프라면, |E(G)|≦2|V(G)|-4이다. (단, |V(G)|≧3)^[21]
G가 평면 그래프라면, |E(G)|≦(κ(|V(G)|-2))/(κ-2)가 성립한다. 여기서 κ는 내주이며, 그래프 G의 최단 폐로 길이이다.^[21]
연결 평면 그래프에 대해, |V(G)|-|E(G)|+f=2가 성립한다. 여기서 |V(G)|는 꼭짓점의 수, |E(G)|는 변의 수, f는 면의 수이다. (오일러 공식)^[21]
종수 g의 곡면 S 위에 그려진 연결 그래프 G가, S를 f개의 영역으로 분할한다고 하자. 이때, |V(G)|-|E(G)|+f=2-2g가 성립한다. ('''오일러 공식''')
그래프가 비평면적인 것은, K_3,3 또는 K₅를 마이너로 포함할 때, 그리고 그 때에 한정된다. ('''바그너의 정리''')
그래프가 평면 그래프일 필요 충분 조건은, 오각형 그래프 또는 육각형 그래프로 축소할 수 있는 그래프를 원래 그래프가 포함하지 않는 것이다. ('''쿠라토프스키 정리''')^[22] 다른 표현으로는, 그래프가 평면 그래프일 필요 충분 조건은, K₅ 또는 K_3,3과 위상 동형인 부분 그래프를 포함하지 않는 것이다.^[21]
평면 그래프의 부분 그래프는 모두 평면 그래프이다.

4. 1. 오일러 공식

연결된 평면 그래프에서 꼭짓점의 수(

v

), 변의 수(

e

), 면의 수(

f

) 사이에는 다음과 같은 관계가 성립한다.

:

v - e + f = 2

이때 면은 변으로 닫힌 유한한 넓이의 면뿐만 아니라, 무한한 넓이의 면도 포함한다. 예를 들어, 꼭짓점 세 개가 서로 연결된 K₃ 그래프에서 면의 수는 2가 된다. 이는 평면 그래프가 구면 위에서 정의되는데, 구면의 오일러 지표가 2이기 때문이다. 평면 그래프의 오일러 지표는 2이다.

오일러 공식은 수학적 귀납법으로 증명할 수 있다. 그래프가 트리가 아니라면, 사이클을 완성하는 변을 제거한다. 이렇게 하면

e

와

f

가 모두 1씩 감소하여

v - e + f

는 일정하게 유지된다. 남은 그래프가 트리가 될 때까지 반복한다. 트리는

v = e + 1

과

f = 1

을 가지며,

v - e + f = 2

를 생성하며, 즉, 오일러 지표는 2이다.

오일러 공식은 볼록 다면체에도 유효하다. 모든 볼록 다면체는 다면체의 슐레겔 도표를 사용하여 연결된 단순 평면 그래프로 변환될 수 있다. 슈타이니츠 정리는 볼록 다면체로부터 형성된 다면체 그래프가 정확히 유한한 3-연결된 단순 평면 그래프라고 말한다.

4. 2. 평균 차수

연결 평면 그래프는 둘 이상의 변을 가지는 경우 부등식 2''e'' ≥ 3''f''를 만족한다. 그 이유는 각 면이 최소 3개의 면-변 발생을 가지며 각 변이 정확히 2개의 발생에 기여하기 때문이다. 이 부등식을 오일러 공식 ''v'' – ''e'' + ''f'' = 2와 함께 대수적으로 변형하면 유한 평면 그래프의 평균 차수는 6보다 작다는 결론이 나온다. 평균 차수가 더 높은 그래프는 평면 그래프가 될 수 없다. 이는 평면 그래프가 희소 그래프임을 의미한다.

4. 3. 밀도

평면 그래프 또는 네트워크의 메시 계수 또는 밀도 ''D''는 유계 면의 수 ''f'' - 1 (그래프의 회로 순위와 동일, 맥 레인 평면성 기준에 따라)를 정점 ''v''를 가진 그래프의 최대 가능한 값 2''v'' - 5로 나눈 값이다.

:D = (f-1)/(2v-5)

밀도는 0 ≤ ''D'' ≤ 1을 따르며, 완전히 희소한 평면 그래프(트리)의 경우 ''D'' = 0이고, 완전히 조밀한 (최대) 평면 그래프의 경우 ''D'' = 1이다.^[3]

4. 4. 쌍대 그래프

교차하는 변이 없이 평면에 연결된 그래프 G^영어의 임베딩이 주어지면, 다음과 같이 쌍대 그래프 G*^영어를 구성할 수 있다. G^영어의 각 면(외부 면 포함)에서 하나의 정점을 선택하고 G^영어의 각 변 e^영어에 대해 G*^영어에서 G^영어에서 e^영어에서 만나는 두 면에 해당하는 두 정점을 연결하는 새로운 변을 도입한다. 이 변은 e^영어를 정확히 한 번 교차하고 G^영어 또는 G*^영어의 다른 변과 교차하지 않도록 그려진다. 그러면 G*^영어는 평면 그래프의 임베딩이 된다. G^영어와 변의 수가 같고, G^영어의 면 수만큼 정점이 있으며, 1=''G''** = ''G''/G}}의 정점 수만큼 면이 있다. "쌍대"라는 용어는 {{math^영어라는 사실에 의해 정당화되며, 여기서 등식은 구에서의 임베딩의 동치이다. G^영어가 볼록 다면체에 해당하는 평면 그래프인 경우 G*^영어는 쌍대 다면체에 해당하는 평면 그래프이다.

쌍대 그래프는 원래 그래프의 속성과 간단한 방식으로 관련되어 있어 쌍대 그래프를 검사하여 그래프에 대한 결과를 증명할 수 있기 때문에 유용하다.

특정 임베딩에 대해 구성된 쌍대는 ( 동형까지) 고유하지만, 그래프는 다른 (즉, 비-위상 동형적인) 임베딩에서 얻은 다른 (즉, 비동형) 쌍대를 가질 수 있다.

4. 5. 기타 성질

사색 정리는 모든 평면 그래프가 4-색칠 가능 (즉, 4-분할 가능)하다고 명시한다.

파리 정리는 모든 단순 평면 그래프가 평면 직선 그래프로 표현될 수 있다고 명시한다. 모든 단순 외평면 그래프는 모든 꼭짓점이 고정된 원 위에 있고 모든 변이 원반 내부에 놓여 교차하지 않는 직선 선분인 평면 내 임베딩을 허용하므로, ''n''개의 꼭짓점을 가진 정다각형은 외평면 그래프에 대해 보편적이다.

샤이너만 추측(현재는 정리)은 모든 평면 그래프가 평면 내 선분의 교차 그래프로 표현될 수 있다고 명시한다.

평면 분리 정리는 모든 ''n''개의 꼭짓점을 가진 평면 그래프를 O()개의 꼭짓점을 제거하여 크기가 최대 2''n''/3인 두 개의 부분 그래프로 분할할 수 있다고 명시한다. 결과적으로, 평면 그래프는 또한 트리 너비와 분기 너비 O()를 갖는다.

평면 곱 구조 정리는 모든 평면 그래프가 트리 너비가 최대 8인 그래프와 경로의 강력한 그래프 곱의 부분 그래프라고 명시한다.^[16] 이 결과는 평면 그래프가 제한된 큐 번호, 제한된 반복적이지 않은 채색수, 그리고 거의 선형 크기의 보편 그래프를 갖는다는 것을 보여주는 데 사용되었다.

''v''개의 꼭짓점을 가진 두 개의 평면 그래프의 경우, 그들이 동형인지 여부를 O(''v'') 시간에 결정하는 것이 가능하다 (그래프 동형 문제도 참조).^[19]

n개의 노드가 있는 모든 평면 그래프는 최대 8(n-2)개의 최대 클리크를 가지며,^[20] 이는 평면 그래프의 클래스가 클리크가 적은 클래스임을 의미한다.

평면 그래프에는 무한 면이 단 하나 있다. 단순 평면 그래프는 차수가 5 이하인 꼭짓점을 갖는다. 평면 그래프의 변의 수는 꼭짓점의 수에 대한 선형 함수로 제한된다. 즉, 평면 그래프에서 |E(G)|≦3|V(G)|-6이다. (단, |V(G)|≧3) 평면 이분 그래프의 변의 수는 꼭짓점의 수에 대한 더 엄격한 선형 함수로 제한된다. 즉, 평면 이분 그래프에서 |E(G)|≦2|V(G)|-4이다. (단, |V(G)|≧3) 평면 그래프의 최단 폐로 길이(내주)를 이용하여 변의 수를 제한할 수 있다.^[21] 즉, 평면 그래프에서 |E(G)|≦(κ(|V(G)|-2))/(κ-2)가 성립한다. (κ는 내주)

연결 평면 그래프에 대해, |V(G)|-|E(G)|+f=2가 성립한다. 여기서 |V(G)|는 꼭짓점의 수, |E(G)|는 변의 수, f는 면의 수이다. (오일러 공식) 종수 g의 곡면 S 위에 그려진 연결 그래프 G가, S를 f개의 영역으로 분할한다고 할 때, |V(G)|-|E(G)|+f=2-2g가 성립한다. ('''오일러 공식''')

그래프가 비평면적인 것은, K_3,3 또는 K₅를 마이너로 포함할 때, 그리고 그 때에 한정된다. ('''바그너의 정리''') 그래프가 평면 그래프일 필요 충분 조건은, 오각형 그래프 또는 육각형 그래프로 축소할 수 있는 그래프를 원래 그래프가 포함하지 않는 것이다. ('''쿠라토프스키 정리''')^[22] 다른 표현으로는, 그래프가 평면 그래프일 필요 충분 조건은, K₅ 또는 K_3,3과 위상 동형인 부분 그래프를 포함하지 않는 것이다. 평면 그래프의 부분 그래프는 모두 평면 그래프이다.

5. 채색

G가 외평면 그래프이면 χ(G) ≦ 3이 성립한다. G가 평면 그래프이면 χ(G) ≦ 4가 성립한다. 이것은 유명한 사색 정리이다. 2-연결 3-평면 정규 그래프는 1-인자 분해할 수 있다. 이것은 사색 정리와 동치이다.

5. 1. 4색정리

평면 그래프는 4개의 색으로 채색 가능하며, 인접한 꼭짓점은 다른 색을 갖는다. 이는 4색정리로 증명되었으며, 컴퓨터를 이용하여 증명되기 전까지 오랜 기간 미해결 문제였다. 2-연결 3-평면 정규 그래프는 1-인자 분해할 수 있다는 것은 사색 정리와 동치이다.

5. 2. 외평면 그래프의 채색

G가 외평면 그래프이면 χ(G) ≦ 3이 성립한다.

5. 3. 평면 정규 그래프의 인자 분해

2-연결 3-평면 정규 그래프는 1-인자 분해할 수 있다. 이것은 사색 정리와 동치이다.

6. 종류

6. 1. 최대 평면 그래프

골드너-해러리 그래프는 극대 평면 그래프이며, 모든 면은 세 개의 모서리로 둘러싸여 있다.

단순 그래프가 평면 그래프이면서, 어떤 모서리 (주어진 정점 집합에서)를 추가하더라도 평면 그래프 성질을 파괴하는 경우 이를 '''극대 평면 그래프'''라고 한다. 모든 면(외부 면 포함)은 세 개의 모서리로 둘러싸여 있으며, 이는 다른 용어인 '''평면 삼각 분할'''을 설명한다 (기술적으로 그래프의 평면 그림을 의미한다).^[4] "삼각 그래프"^[4] 또는 "삼각화 그래프"^[5]라는 다른 이름도 사용되었지만, 이는 모호한데, 완전 그래프의 선 그래프와 현 그래프를 각각 더 일반적으로 지칭하기 때문이다. 3개 이상의 정점을 가진 모든 극대 평면 그래프는 3-연결 이상이다.^[6]

극대 평면 그래프가 ''v''개의 정점을 가지고 ''v'' > 2일 경우, 정확히 3''v'' – 6개의 모서리와 2''v'' – 4개의 면을 갖는다.

아폴로니안 네트워크는 극대 평면 그래프의 한 예시이다.

교살 그래프는 모든 주변 주기가 삼각형인 그래프이다. 극대 평면 그래프 (또는 더 일반적으로 다면체 그래프)에서 주변 주기는 면이므로 극대 평면 그래프는 교살 그래프이다. 교살 그래프는 또한 현 그래프를 포함하며, 완전 그래프 및 극대 평면 그래프의 클리크 합 (모서리 삭제 없이)에 의해 형성될 수 있는 그래프와 정확히 같다.^[7]

6. 2. 외평면 그래프

외면 그래프는 평면에 포함되어 모든 정점이 무한 면에 속하는 그래프이다.^[8] 모든 외면 그래프는 평면 그래프이지만 그 역은 성립하지 않는데, ''K''₄는 평면 그래프이지만 외면 그래프는 아니다.^[8] 쿠라토프스키 정리와 유사한 정리에 따르면 유한 그래프가 외면 그래프인 것은 ''K''₄ 또는 ''K''_2,3의 세분 그래프를 포함하지 않는 경우와 필요충분조건이다.^[8] 이는 그래프 ''G''에 새로운 정점을 추가하여 형성된 그래프가 평면 그래프일 경우, 즉 다른 모든 정점과 연결되는 간선을 갖는 그래프가 외면 그래프라는 사실의 직접적인 결과이다.^[8]

그래프의 1-외면 포함은 외면 포함과 동일하다. ''k'' > 1에 대해 평면 포함은 외면 면의 정점을 제거하면 (''k'' – 1)-외면 포함이 되는 경우 ''k''-외면이다. 그래프가 ''k''-외면 포함을 가지면 ''k''-외면이다.

극대 외평면 그래프는 절단점이 없고 무한면 이외의 면이 모두 삼각형이 되도록 평면에 그릴 수 있다.
극대 외평면 그래프 G의 변 e=xy에 대해, e가 현(무한대에 면하지 않은 변)인 경우 G-{x,y}가 비연결이다.
3점 이상의 극대 외평면 그래프에는 차수 2의 점이 있다.
G가 2점 이상의 극대 외평면 그래프라면, |E(G)| = 2・|G|-3이 성립한다.

6. 3. 할린 그래프

할린 그래프는 차수 2인 노드가 없는 평면 트리에서 파생된 그래프로, 나무의 평면 임베딩에 의해 주어진 순서대로 잎을 주기로 연결하여 형성된다.^[9] 동등하게, 이는 하나의 면이 다른 모든 면에 인접한 다면체 그래프이다.^[9] 모든 할린 그래프는 평면 그래프이다.^[9] 외곽 평면 그래프와 마찬가지로, 할린 그래프는 낮은 트리 폭을 가지므로, 제한 없는 평면 그래프보다 많은 알고리즘 문제를 더 쉽게 해결할 수 있다.^[9]

6. 4. 상향 평면 그래프

상향 평면 그래프는 방향 비순환 그래프의 일종으로, 평면상에 교차하지 않는 곡선으로 가장자리를 표현하며, 모든 가장자리가 일관되게 위쪽 방향으로 향하도록 그릴 수 있는 그래프를 의미한다. 모든 평면 방향 비순환 그래프가 상향 평면 그래프인 것은 아니며, 주어진 그래프가 상향 평면 그래프인지 여부를 검사하는 문제는 NP-완전 문제이다.

6. 5. 볼록 평면 그래프

평면 그래프의 모든 면(외부 면 포함)이 볼록 다각형이면 해당 그래프를 '''볼록'''이라고 한다. 모든 평면 그래프가 볼록 임베딩을 갖는 것은 아니다(예: 완전 이분 그래프 K_2,4). 그래프를 볼록하게 그릴 수 있는 충분 조건은 그래프가 3-정점 연결 평면 그래프의 세분인 경우이다. Tutte의 스프링 정리에 따르면 간단한 3-정점 연결 평면 그래프의 경우 내부 정점의 위치를 인접 정점들의 평균으로 선택할 수 있다.

6. 6. 단어-표현 가능 평면 그래프

단어-표현 가능 평면 그래프에는 삼각-자유 평면 그래프와 더 일반적으로 3-채색 가능한 평면 그래프^[10], 삼각 그리드 그래프의 특정 면 분할^[11], 그리드 덮인 실린더 그래프의 특정 삼각화가 포함된다.^[12]

7. 정리

7. 1. 평면 그래프의 개수

n

개의 정점을 가진 평면 그래프의 수는 점근적 분석에 따르면

g\cdot n^{-7/2}\cdot \gamma^n\cdot n!

이다. 여기서

\gamma\approx 27.22687

이고

g\approx 0.43\times 10^{-5}

이다.^[13]

거의 모든 평면 그래프는 지수적으로 많은 자기 동형 사상을 갖는다.^[14]

n

개의 정점을 가진 라벨이 지정되지 않은 (비동형) 평면 그래프의 수는

27.2^n

과

30.06^n

사이에 있다.^[15]

7. 2. 기타 정리

파리 정리는 모든 단순 평면 그래프가 평면 직선 그래프로 표현될 수 있다고 명시한다.^[16] 보편적인 점 집합은 모든 평면 그래프가 해당 점 집합 내에 모든 꼭짓점을 가진 임베딩을 갖는 점 집합이다.

샤이너만 추측(현재는 정리)은 모든 평면 그래프가 평면 내 선분의 교차 그래프로 표현될 수 있다고 명시한다.

평면 분리 정리는 모든 ''n''개의 꼭짓점을 가진 평면 그래프를 O()개의 꼭짓점을 제거하여 크기가 최대 2''n''/3인 두 개의 부분 그래프로 분할할 수 있다고 명시한다. 결과적으로, 평면 그래프는 또한 트리 너비와 분기 너비 O()를 갖는다.

평면 곱 구조 정리는 모든 평면 그래프가 트리 너비가 최대 8인 그래프와 경로의 강력한 그래프 곱의 부분 그래프라고 명시한다.^[16] 이 결과는 평면 그래프가 제한된 큐 번호, 제한된 반복적이지 않은 채색수, 그리고 거의 선형 크기의 보편 그래프를 갖는다는 것을 보여주는 데 사용되었다.^[17]^[18]

''v''개의 꼭짓점을 가진 두 개의 평면 그래프의 경우, 그들이 동형인지 여부를 O(''v'') 시간에 결정하는 것이 가능하다 (그래프 동형 문제도 참조).^[19]

n개의 노드가 있는 모든 평면 그래프는 최대 8(n-2)개의 최대 클리크를 가지며,^[20] 이는 평면 그래프의 클래스가 클리크가 적은 클래스임을 의미한다.

8. 일반화

정점 그래프는 하나의 정점을 제거하여 평면 그래프로 만들 수 있는 그래프이며, ''k''-정점 그래프는 최대 ''k''개의 정점을 제거하여 평면 그래프로 만들 수 있는 그래프이다. 1-평면 그래프는 각 변마다 최대 하나의 단순 교차점을 갖는 평면상에 그릴 수 있는 그래프이며, ''k''-평면 그래프는 각 변마다 최대 ''k''개의 단순 교차점을 갖는 평면상에 그릴 수 있는 그래프이다.

지도 그래프는 평면에서 유한 개의 단순히 연결된 내부 분리 영역 집합으로부터, 두 영역이 적어도 하나의 경계점을 공유할 때 두 영역을 연결하여 형성된 그래프이다. 한 점에서 최대 세 개의 영역이 만나면 평면 그래프가 되지만, 네 개 이상의 영역이 한 점에서 만나면 평면 그래프가 아닐 수 있다. 예를 들어, 원을 부채꼴로 나누고 부채꼴을 영역으로 생각하면, 해당 지도 그래프는 모든 부채꼴이 공통 경계점인 중심점을 갖기 때문에 완전 그래프가 된다.

토러스 그래프는 토러스에서 교차 없이 임베딩될 수 있는 그래프이다. 더 일반적으로, 그래프의 종수는 그래프를 임베딩할 수 있는 2차원 표면의 최소 종수이다. 평면 그래프는 종수가 0이고, 비평면 토러스 그래프는 종수가 1이다. 모든 그래프는 (가향, 연결) 폐2차원 표면(손잡이가 있는 구)에 교차 없이 임베딩될 수 있으므로, 그래프의 종수는 잘 정의된다. 분명히, 그래프가 종수 g인 (가향, 연결, 닫힌) 표면에 교차 없이 임베딩될 수 있다면, 종수가 g보다 크거나 같은 모든 (가향, 연결, 닫힌) 표면에 교차 없이 임베딩될 수 있다. "X"가 일부 한정사인 "X 종수"라고 불리는 그래프 이론의 다른 개념도 있다. 일반적으로 이들은 한정사 없이 위에 정의된 "종수"의 개념과 다릅니다. 특히 그래프의 비가향 종수(정의에서 비가향 표면을 사용)는 일반적인 그래프의 종수(정의에서 가향 표면을 사용)와 다릅니다.

모든 그래프는 3차원 공간에 교차 없이 임베딩될 수 있다. 실제로, 모든 그래프는 2개의 평면 설정에서 교차 없이 그릴 수 있다. 여기서 두 평면은 서로 위에 배치되고, 변은 (그래프 정점이 아닌) 어느 곳에서든 한 평면에서 다른 평면으로 "점프"하여 "떨어질" 수 있으므로, 변이 다른 변과의 교차를 피할 수 있다. 이는 임의의 전기 전도체 네트워크를 양면 회로 기판으로 만들 수 있음을 의미한다. 여기서 보드의 양면 사이의 전기적 연결을 만들 수 있다(전선의 조각을 통해 보드의 상단에서 전기적 연결을 수행하고, 보드 자체에 구성된 구리 트랙을 통해 하단에서 수행하고, 구멍을 뚫고, 구멍을 통해 전선을 통과시키고, 납땜하여 트랙에 연결하는 방식으로 일반적인 실제 회로 기판과 같이). 또한 이는 임의의 도로 네트워크를 구축하기 위해 다리나 터널만 있으면 되며, 둘 다 필요하지 않다는 것을 의미할 수 있다(2단계로 충분하며, 3단계는 필요하지 않음). 또한 3차원에서는 교차 없이 그래프를 그리는 문제는 사소하다. 그러나 평면 그래프의 3차원 유사체는 링크 없는 임베딩 가능 그래프에 의해 제공된다. 링크 없는 임베딩 가능 그래프는 두 개의 사이클이 서로 위상적으로 연결되지 않도록 3차원 공간에 임베딩될 수 있는 그래프이다. 평면 그래프를 마이너로 ''K''₅ 또는 ''K''_3,3을 포함하지 않는 그래프로 특징짓는 쿠라토프스키와 바그너의 특성화에 비추어, 링크 없는 임베딩 가능 그래프는 페테르센 패밀리의 일곱 개 그래프 중 어느 것도 마이너로 포함하지 않는 그래프로 특징지을 수 있다. 외부 평면 그래프 및 평면 그래프를 콜린 드 베르디에 그래프 불변량이 최대 2 또는 3인 그래프로 특징짓는 것과 유사하게, 링크 없는 임베딩 가능 그래프는 콜린 드 베르디에 불변량이 최대 4인 그래프이다.

8. 1. 정점 그래프

8. 2. k-평면 그래프

8. 3. 지도 그래프

8. 4. 토러스 그래프

8. 5. 링크 없는 임베딩 가능 그래프

9. 용어

; 면

: 평면 그래프에서 변으로 둘러싸인 극소 영역。 유계인 면을 '''유한면''' , 유계가 아닌 면을 '''무한면''' 이라고 부른다.

; 다각형망(polygonal net)

: 평면을 다각형 조각으로 분할하는 평면의 연결된 다각형의 둘레 집합 (이러한 다각형의 둘레의 변은 직선일 필요는 없다.)

; 다각형 그래프(polygonal graph)

: 그 변이 평면에서 어느 다각형도 다른 다각형을 완전히 둘러싸지 않는 다각형망을 만드는 평면 그래프.

; 다각형 그래프 G의 쌍대 그래프 G* (dual graph G* of a polygonal graph G)

: 그 정점이 G의 면에, 그 면이 G의 정점에 대응하는 다각형 그래프 G*를 말한다. G*의 두 정점은 G의 면이 하나의 경계 변을 공유할 때 연결된다.

; 외평면 그래프

: 모든 정점이 무한면 주위에 오도록 그릴 수 있는 평면 그래프。 이 중 변 집합이 극대인 것은 '''극대 외평면 그래프''' 라고 불린다

9. 1. 면

평면 그래프에서 변으로 둘러싸인 극소 영역이다. 유계인 면을 '''유한면''', 유계가 아닌 면을 '''무한면'''이라고 부른다.

9. 2. 다각형망

평면 그래프에서 다각형망은 평면을 다각형 조각으로 분할하는 평면의 연결된 다각형의 둘레 집합이다. 이러한 다각형의 둘레의 변은 직선일 필요는 없다.

9. 3. 다각형 그래프

다각형 그래프는 그 변이 평면에서 어느 다각형도 다른 다각형을 완전히 둘러싸지 않는 다각형망을 만드는 평면 그래프이다. 다각형 그래프 G의 쌍대 그래프 G*는 그 정점이 G의 면에, 그 면이 G의 정점에 대응하는 다각형 그래프를 말한다. G*의 두 정점은 G의 면이 하나의 경계 변을 공유할 때 연결된다.

참조

_[1] 서적 Introduction to Graph Theory http://store.doverpu[...] Dover Pub. 2012-08-08
_[2] 서적 Morphogenesis of Spatial Networks Springer 2017
_[3] 간행물 Efficiency and robustness in ant networks of galleries
_[4] 간행물 Planar graphs and poset dimension
_[5] 간행물 A linear algorithm to find a rectangular dual of a planar triangulated graph
_[6] 간행물 On the connectivity of maximal planar graphs
_[7] 간행물 A generalization of chordal graphs
_[8] 간행물 Geometric graphs and arrangements Friedr. Vieweg & Sohn, Wiesbaden
_[9] 간행물 Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981 Springer-Verlag
_[10] 간행물 Semi-transitive orientations and word-representable graphs https://strathprints[...] 2016
_[11] 간행물 Word-representability of face subdivisions of triangular grid graphs 2016
_[12] 간행물 Word-representability of triangulations of grid-covered cylinder graphs 2016
_[13] 간행물 Asymptotic enumeration and limit laws of planar graphs
_[14] 간행물 Random planar graphs
_[15] 간행물 Planar Graphs, via Well-Orderly Maps and Trees
_[16] 간행물 Planar graphs have bounded queue number
_[17] 간행물 Asymptotically optimal vertex ranking of planar graphs
_[18] 간행물 Improved Bounds for Centered Colorings
_[19] 서적 Proceedings of the 12th Annual ACM Symposium on Theory of Computing https://hal.inria.fr[...]
_[20] 문서 On the Maximum Number of Cliques in a Graph https://doi.org/10.1[...] Graphs and Combinatorics 2007
_[21] 문서 井上(2007)
_[22] 문서 オア(1970)

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com