외부 평면 그래프
Outerplanar graph
그래프 이론에서 외부 평면 그래프는 모든 정점이 도면의 바깥 면에 속하는 평면 도면을 갖는 그래프다.
외부 평면 그래프는 금지된 두 미성년자 K와4 K2,3, 또는 그들의 콜린 드 베르디에르 그래프 불변성에 의해 특징지어질 수 있다(평면 그래프에 대한 바그너의 정리와 유사).그들은 만약 그들이 바이코넥트된 경우에만 해밀턴 사이클을 가지고 있고, 이 경우 외부 표면은 독특한 해밀턴 사이클을 형성한다.모든 외부 평면 그래프는 3색이며, 최대 2색까지 퇴행성과 나무 너비가 있다.
외부 평면 그래프는 평면 그래프, 열-병렬 그래프의 하위 그래프 및 원 그래프의 하위 집합이다.최대 외관 그래프는 외관성을 보존하면서 더 이상 가장자리를 추가할 수 없는 그래프도 화음 그래프와 가시성 그래프다.
역사
외부 평면 그래프는 한 기본 그래프의 두 복사본을 연결하기 위해 완벽한 일치를 사용하여 형성된 그래프의 평면성을 결정하는 문제와 관련하여, Chartrand & Harary(1967)에 의해 처음으로 연구되고 명명되었다(예를 들어, 일반화된 Petersen 그래프 중 많은 부분이 한 사이클 그래프의 두 복사본에서 이러한 방식으로 형성된다.그들이 보여 준 것처럼, 베이스 그래프가 양방향으로 연결되었을 때, 만약 그것의 베이스 그래프가 외부 평면이고 매칭이 그것의 외부 주기의 일방향 순열을 형성하는 경우에만 이러한 방식으로 구성된 그래프가 평면이다.차르트랑과 하라리는 또한 외부 평면 그래프에 대한 쿠라토프스키의 정리의 아날로그를 증명했는데, 두 그래프 중 K4 또는 K의2,3 하위분할을 포함하지 않는 경우에만 그래프가 외부 평면이라는 것을 증명했다.
정의 및 특성화
외부 평면 그래프는 모든 정점이 도면의 무한 면에 속하도록 교차 없이 평면에서 그릴 수 있는 비방향 그래프다.즉, 어떤 꼭지점도 완전히 가장자리에 둘러싸여 있지 않다.또는 다른 모든 정점에 가장자리가 연결된 새로운 정점을 추가하여 G에서 형성된 그래프가 평면 그래프인 경우 그래프 G는 외부 평면이다.[1]
최대 외부 평면 그래프는 외부 평면도를 보존하면서 추가 가장자리를 추가할 수 없는 외부 평면 그래프다.정점이 n개인 최대 외부 평면 그래프는 정확히 2n - 3 가장자리를 가지며, 최대 외부 평면 그래프의 경계면은 삼각형이다.
금지 그래프
외부 평면 그래프는 쿠라토프스키의 정리 및 평면 그래프의 바그너의 정리와 유사한 금지된 그래프 특성을 가지고 있다: 완전한 그래프 K4 또는 완전한 양분 그래프 K의2,3 하위분할을 포함하지 않는 경우에만 그래프가 외부 평면이다.[2]또는 K 또는4 K를2,3 부차적으로 포함하지 않는 경우에만 그래프가 외부 평면이며, 가장자리를 삭제하고 수축하여 그래프를 얻는다.[3]
삼각형이 없는 그래프는 K의2,3 하위분할을 포함하지 않는 경우에만 외부 평면이다.[4]
콜린 드 베르디에르 불변제
그래프는 콜린 드 베르디에르 그래프의 불변성이 최대 2인 경우에만 외부 평면이다.그래프는 콜린 드 베르디에르 불변성을 최대 1개, 3개 또는 4개로 하여 유사한 방식으로 특징지어지는 것이 각각 선형 숲, 평면 그래프, 연결성 없이 내장 가능한 그래프들이다.
특성.
바이오넥티시티와 해밀턴시티
외부 평면 그래프는 그래프의 외부 표면이 정점이 반복되지 않는 단순한 주기를 형성하는 경우에만 양방향으로 연결된다.외측 평면 그래프는 양방향 연결인 경우에만 해밀턴식 그래프인데, 이 경우 외측면이 독특한 해밀턴식 사이클을 형성한다.[5]보다 일반적으로, 외부 평면 그래프에서 가장 긴 주기의 크기는 가장 큰 이콘넥트 성분의 정점 수와 같다.이러한 이유로 임의 그래프에 대한 이러한 문제의 NP-완전성과는 대조적으로 외부 평면 그래프의 해밀턴 주기 및 최장 주기 발견은 선형 시간 내에 해결될 수 있다.
모든 최대 외부 평면 그래프는 해밀턴성보다 더 강한 조건을 만족한다: 그것은 노드 범순환이다. 즉, 모든 꼭지점 v와 그래프에서 3부터 정점 수까지의 범위에 있는 모든 k에 대해, v를 포함하는 길이-k 사이클이 있다는 것을 의미한다.이 길이의 주기는 단일 에지로 그래프의 나머지 부분에 연결된 삼각형을 반복적으로 제거하여 나머지 그래프의 바깥 면에 길이 k가 될 때까지 제거된 정점이 v가 되도록 함으로써 찾을 수 있다.[6]
평면 그래프는 각각의 2차원 구성요소가 외부 평면인 경우에만 외부 평면이다.[4]
컬러링
모든 반복되지 않는 외부 평면 그래프는 세 가지 색상만 사용하여 색칠할 수 있다.[7] 이 사실은 피스크(1978년)에 의한 차바탈의 미술관 정리 간소화된 증거에서 두드러지게 나타난다.3-색상은 탐욕스러운 컬러링 알고리즘에 의해 선형 시간에 발견될 수 있는데, 이 알고리즘은 최대 2도에서 정도 정점을 제거하고, 남은 그래프를 반복적으로 색칠한 다음, 제거된 정점을 두 이웃의 색과 다른 색으로 다시 추가하는 것이다.
Vizing의 정리에 따르면, 어떤 그래프의 색지수(가장자리를 색칠하는 데 필요한 최소 색상 수)는 그래프의 정점에 대한 최대도 또는 1+최대도 중 하나이다.그러나 연결된 외부 평면 그래프에서 색도 지수는 그래프가 홀수 길이의 주기를 형성하는 경우를 제외하고 최대도와 동일하다.[8]최적의 색상 수를 가진 가장자리 색상은 약한 이중 트리의 너비 우선 통과에 기초하여 선형 시간에 찾을 수 있다.[7]
기타 속성
외부 평면 그래프는 최대 두 개까지 퇴보한다. 즉, 외부 평면 그래프의 모든 하위 그래프에는 최대 두 개의 정도가 있는 꼭지점이 포함되어 있다.[9]
외부 평면 그래프는 최대 2개의 트리 너비를 가지며, 임의 그래프에 대해 NP-완전한 많은 그래프 최적화 문제는 입력이 외부 평면일 때 동적 프로그래밍에 의해 다항식 시간에 해결될 수 있음을 의미한다.보다 일반적으로 k-outerplanar 그래프는 나무 너비 O(k)를 가진다.[10]
모든 외부 평면 그래프는 평면 내 축 정렬 직사각형의 교차 그래프로 나타낼 수 있으므로 외부 평면 그래프는 최대 2개의 박스성을 가진다.[11]
관련 그래프 패밀리
모든 외부 평면 그래프는 평면 그래프다.모든 외부 평면 그래프는 직렬-병렬 그래프의 하위 그래프이기도 하다.[12]그러나 모든 평면 시리즈-병렬 그래프가 외부 평면 그래프는 아니다.완전한 초당적 그래프 K는2,3 평면과 직렬-병렬이지만 외부 평면도는 아니다.반면에 전체 그래프 K는4 평면이지만 직렬-병렬도, 외부 평면도 아니다.모든 숲과 선인장 그래프는 외부 행성이다.[13]
내장된 외부 평면 그래프의 약한 평면 이중 그래프(내장된 각 경계면마다 꼭지점과 인접 경계면 쌍마다 가장자리가 있는 그래프)는 숲이며, 할린 그래프의 약한 평면 이중은 외부 평면 그래프다.평면 그래프는 약한 이중성이 숲인 경우만 외부 평면이며, 약한 이중성이 양면체 및 외부 평면인 경우에만 할린이다.[14]
외부 행성 정도라는 개념이 있다.그래프를 포함하는 1-외부는 외부 평면 임베딩과 동일하다.k > 1의 경우 외부 표면의 정점을 제거하면 (k - 1)-외측 평면 임베딩이 되는 경우 평면 임베딩은 k-외측 평면이라고 한다.그래프는 k-outerplanar 내장형인 경우 k-outerplanar이다.[15]
1-평면 그래프와 유사한 외부 1-평면 그래프는 디스크 경계에 정점이 있고 에지당 교차점이 최대 1개 있는 디스크에 그릴 수 있다.
모든 최대 외부 행성 그래프는 화음 그래프다.모든 최대 외부 평면 그래프는 단순한 다각형의 가시성 그래프다.[16]최대 외부 평면 그래프는 다각형 삼각형의 그래프로도 형성된다.이들은 2-tree, 직렬-병렬 그래프 및 코드 그래프의 예들이다.
모든 외부 평면 그래프는 원의 화음 집합의 교차 그래프인 원 그래프다.[17]
메모들
- ^ 펠스너(2004년).
- ^ Chartrand & Harary(1967); Syswo(1979); Brandstedt, Le & Spinrad(1999); Proposition 7.3.1, 페이지 117; Felsner(2004).
- ^ 디에스텔(2000년)
- ^ a b 시스와우(1979년).
- ^ 샤르트랑&하라리(1967년), 시스와우(1979년).
- ^ Li, Corneil & Mendelson(2000), 발의안 2.5.
- ^ a b 프로스쿠로스키&시스와우(1986)
- ^ 피오리니(1975년).
- ^ 릭&화이트(1970년).
- ^ 베이커(1994년).
- ^ Scheinerman(1984); Brandstédt, Le & Spinrad(1999), 페이지 54.
- ^ Brandstédt, Le & Spinrad(1999), 페이지 174.
- ^ Brandstédt, Le & Spinrad(1999), 페이지 169.
- ^ 시스와프 & 프로스쿠로우스키(1983년).
- ^ 케인&바수(1976년), 시스와우(1979년).
- ^ 엘진디(1985) 린&스키에나(1995) 브랜스테트, 르&스피프라드(1999), 정리 4.10.3, 페이지 65.
- ^ 웨셀&포셸(1985); 웅거(1988).
참조
- Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID 9706753.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "The problem of outer embeddings in pseudosurfaces", Ars Combinatoria, 71: 79–91.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "Obstruction sets for outer-bananas-surface graphs", Ars Combinatoria, 73: 65–77.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2006), "Uncountable graphs with all their vertices in one face", Acta Mathematica Hungarica, 112 (4): 307–313, doi:10.1007/s10474-006-0082-0, S2CID 123241658.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2010), "Outer-embeddability in certain pseudosurfaces arising from three spheres", Discrete Mathematics, 310 (23): 3359–3367, doi:10.1016/j.disc.2010.07.027.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, ISBN 0-89871-432-X.
- Chartrand, Gary; Harary, Frank (1967), "Planar permutation graphs", Annales de l'Institut Henri Poincaré B, 3 (4): 433–438, MR 0227041.
- Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, p. 107, ISBN 0-387-98976-5.
- El-Gindy, H. (1985), Hierarchical decomposition of polygons with applications, Ph.D. thesis, McGill University. Brandstedt가 인용한 바와 같이, Le & Spinrad(1999년).
- Felsner, Stefan (2004), Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, p. 6, ISBN 978-3-528-06972-8.
- Fiorini, Stanley (1975), "On the chromatic index of outerplanar graphs", Journal of Combinatorial Theory, Series B, 18 (1): 35–38, doi:10.1016/0095-8956(75)90060-X.
- Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X.
- Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society, 38: 215–219, MR 0389672.
- Kane, Vinay G.; Basu, Sanat K. (1976), "On the depth of a planar graph", Discrete Mathematics, 14 (1): 63–67, doi:10.1016/0012-365X(76)90006-6.
- Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics, 98 (3): 219–225, doi:10.1016/S0166-218X(99)00163-8.
- Lick, Don R.; White, Arthur T. (1970), "k-degenerate graphs", Canadian Journal of Mathematics, 22 (5): 1082–1096, doi:10.4153/CJM-1970-125-1.
- Lin, Yaw-Ling; Skiena, Steven S. (1995), "Complexity aspects of visibility graphs", International Journal of Computational Geometry and Applications, 5 (3): 289–312, doi:10.1142/S0218195995000179.
- Proskurowski, Andrzej; Sysło, Maciej M. (1986), "Efficient vertex-and edge-coloring of outerplanar graphs", SIAM Journal on Algebraic and Discrete Methods, 7: 131–136, doi:10.1137/0607016.
- Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters of a Graph, Ph.D. thesis, Princeton University. Brandstedt가 인용한 바와 같이, Le & Spinrad(1999년).
- Sysło, Maciej M. (1979), "Characterizations of outerplanar graphs", Discrete Mathematics, 26 (1): 47–53, doi:10.1016/0012-365X(79)90060-8.
- Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
- Unger, Walter (1988), "On the k-colouring of circle-graphs", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, vol. 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832.
- Wessel, W.; Pöschel, R. (1985), "On circle graphs", in Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, Teubner-Texte zur Mathematik, vol. 73, B.G. Teubner, pp. 207–210. 웅거(1988)가 인용한 바와 같다.
외부 링크
- 정보 시스템의 그래프 클래스 및 포함에 대한 외부 평면 그래프
- Weisstein, Eric W. "Outplanar Graph". MathWorld.
