그래프 삽입

Graph embedding
토러스에 내장된 휴우드 그래프와 관련 지도.

위상그래프이론에서 G\Sigma})의 표면{\({ \에 삽입(임베딩이라고도 함) 것은 \Sigma의 GG})를 단순하게 홈 및 정점과 연관시킨 표현이다.[ , { , }ic 이미지는 다음과 같은 방법으로 에지와 연결됩니다.

  • 와 관련된 호 끝점은e의 정점과 관련된 점 {\ e
  • 호는 다른 정점과 연관된 점을 포함하지 않습니다.
  • 두 호는 두 호 중 어느 호 안쪽에 있는 점에서 절대 교차하지 않습니다.

여기 표면은 콤팩트하고 연결된의 매니폴드입니다

비공식적으로 그래프를 지표면에 삽입하는 것은 가장자리가 끝점에서만 교차할 수 있는 방식으로 지표면에 그래프를 그리는 것입니다.유한 그래프는 3차원 유클리드 ^{[1]에 삽입할 수 있다는 것은 잘 알려져 있다. 평면 그래프는 2차원 유클리드 삽입할 수 있는 그래프이다2}

임베딩은 종종 방금 설명한 종류의 표현의 동등성 클래스( ( \ 의 동형사상 아래)로 간주됩니다.

일부 작성자는 모서리에 대해 교차하지 않는 조건을 생략하여 "그래프 내장" 정의의 더 약한 버전을 정의합니다.이러한 맥락에서 보다 엄격한 정의는 "비교차 그래프 삽입"[2]으로 설명됩니다.

이 기사에서는 그래프 임베딩의 엄격한 정의만을 다룬다.더 약한 정의는 "그래프 도면" 및 "교차 번호" 기사에서 설명합니다.

용어.

G(\ G가 닫힌 표면(\에 삽입되어 있는 경우 G(\G)의 정점과 모서리와 관련된 점과 호의 합은 영역(또는 면)[3]의 집합이다.2셀 임베딩, 셀 임베딩 또는 맵은 모든 면이 오픈 [4]디스크와 동형인 임베딩입니다.폐쇄형 2셀 매립은 모든 면의 폐쇄가 폐쇄형 디스크와 동형인 매립이다.

그래프의 속은n속n의 표면에 그래프를 삽입할 수 있는 최소 n(\ n이며, 특히 평면 그래프는 0 0의 속(\displaystyle 0)을 가지며, 이는 자기교차 없이 구면에 그릴 수 있기 때문이다.그래프의 비방향성 속은 (비방향성) n\[3]n의 비방향성 표면에 그래프를 삽입할 수 있는 정수n\displaystylen입니다.

그래프의 오일러 속은 최소 n 이며 그래프는 n/2n/2 nn 속 n({displaystyle n})의 방향성 없는 표면에 포함될 수 있다. 오일러 속보다 작을 경우 방향성할 수 있다.방향성이 없는 속

그래프의 최대 속은 최대 n(\ n입니다.그래프는 n n의 방향성 표면에 22) 셀을 할 수 있습니다.

조합 매립

주요 기사: 로테이션 시스템

내장된 그래프는 동일한 정점에 입사하는 에지의 순환 순서를 고유하게 정의한다.이 모든 순환 순서의 집합을 회전 시스템이라고 합니다.동일한 회전 시스템을 가진 임베딩은 동등하다고 간주되며, 임베딩의 대응하는 등가 클래스는 조합 임베딩이라고 불린다(점 및 곡선의 관점에서 이전의 정의를 참조하는 위상 임베딩이라는 용어와 반대).때때로 회전 시스템 자체를 "공역 매립"[5][6][7]이라고 합니다.

임베디드 그래프는 임베디드 면의 경계를 구성하는 에지의 자연스러운 순환 순서를 정의한다.그러나 일부 가장자리가 면 경계를 따라 두 번 횡단될 수 있으므로 이러한 면 기반 주문을 처리하는 것이 덜 간단합니다.예를 들어, 이것은 단일 면을 가진 나무를 심는 경우 항상 해당됩니다.이러한 조합상의 문제를 해결하려면 모든 에지가 두 개의 "하프 에지" 또는 "사이드"로 세로로 "분할"된 것으로 간주할 수 있습니다.이 규칙에 따르면 모든 면 경계 트래버스에서 각 하프 에지는 한 번만 통과되고 동일한 에지의 두 하프 에지는 항상 반대 방향으로 통과됩니다.

셀룰러 임베딩을 위한 다른 등가 표현으로는 리본 그래프, 임베디드 그래프의 정점과 엣지에 대한 위상 디스크를 접착함으로써 형성되는 위상 공간 및 임베디드 그래프의 각 엣지에 대해 4개의 정점을 갖는 엣지 색상의 입방 그래프인 그래프 부호화 맵이 있다.

계산의 복잡성

그래프 속성을 찾는 문제는 NP-hard이다n\ nvertex 에 g가 있는지 확인하는 문제는 NP-complete).[8]

동시에 그래프 속 문제는 고정 파라미터 추적가능하며, 즉 다항시간 알고리즘은 그래프를 특정 고정속 표면에 삽입할 수 있는지 여부를 체크하고 삽입물을 찾는 것으로 알려져 있다.

이 점에서 첫 번째 돌파구는 1979년 시간 복잡도 O(nO(g)) 알고리즘이 독립적으로 컴퓨팅 이론에 관한 연례 ACM 심포지엄에 제출되었을 때 일어났다.필로티와 G.L. 밀러 그리고 존 레이프의 또 다른 작품입니다.그들의 접근 방식은 상당히 달랐지만, 프로그램 위원회의 제안에 따라 그들은 공동 [9]논문을 발표했다.그러나 웬디 미르볼드와 윌리엄 코케이는 2011년 필로티, 밀러, 레이프가 제공한 알고리즘이 [10]틀렸다는 것을 증명했다.

1999년에는 그래프 크기에서 시간 선형으로 해결되고 [11]속에서는 두 배로 기하급수적으로 해결될 수 있다고 보고되었다.

고차원 공간에 그래프 삽입

유한한 그래프는 3차원 [1]공간에 삽입할 수 있는 것으로 알려져 있다.

이를 위한 한 가지 방법은 공간의 임의의 선에 점을 배치하고 모서리를 곡선으로 그리는 것입니다. 곡선은 각각 개별 하프플레인에 있으며 모든 하프플레인은 해당 선을 공통 경계로 가지고 있습니다.가장자리가 반평면에 그려지는 이와 같은 임베딩을 그래프의 북 임베딩이라고 합니다.이 비유는 모서리가 그려진 각각의 평면들이 책의 한 페이지와 같다고 상상하는 것에서 유래한다.실제로 여러 모서리가 동일한 "페이지"에 그려질 수 있다는 것이 관찰되었다. 그래프의 책 두께는 이러한 도면에 필요한 최소 반평면 수이다.

또는 4개의 정점을 동일평면이 되지 않도록 일반적인 위치에 배치함으로써 교차하지 않고 3차원의 직선 가장자리를 사용하여 임의의 유한 그래프를 그릴 수 있다.예를 들어, 이것은 모멘트 곡선의 점(i,i,i2)에3 ih 정점을 배치함으로써 달성될 수 있다.

두 개의 사이클이 위상적으로 연결되어 있지 않은 3차원 공간에 그래프를 내장하는 것을 링크리스 내장이라고 한다.그래프에는 마이너로서 Petersen 패밀리의 7개의 그래프 중 하나가 없는 경우에만 링크가 없는 임베딩이 있습니다.

갤러리

  • The Petersen graph and associated map embedded in the projective plane. Opposite points on the circle are identified yielding a closed surface of non-orientable genus 1.

    투영 평면에 포함된 Petersen 그래프 및 관련 지도.원상의 반대점을 특정하여 비방향성속 1의 폐쇄면을 생성한다.

  • The Pappus graph and associated map embedded in the torus.

    토러스에 내장된 Pappus 그래프 및 관련 맵.

  • The degree 7 Klein graph and associated map embedded in an orientable surface of genus 3.

    7도 클라인 그래프와 관련 지도는 3속 방향성 표면에 내장되어 있다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b 코헨, 로버트 F.;Eades, 피터, 린, 도;Ruskey, 프랭크(1995년),"3차원 그래프 그리기", Tamassia, 로베르토에;Tollis, 요안 니스 G.(eds.)Graph도면:DIMACS 국제 워크숍 GD'94은 뉴저지 프린스턴 대학, 미국, 10월 10–12, 1994년, 회보, 강의 노트 컴퓨터 과학으로, 894년 vol., 스프링거,를 대신하여 서명함. 1–11,. doi:10.1007/3-540-58950-3_351, 아이 에스비엔 978-3-540-58950-1.
  2. ^ 는 Katoh, 나오키, Tanigawa, Shin-ichi(2007년),"구속된 Non-crossing 기하학적 신장의 나무들 Enumerating", 컴퓨팅과 조합론, 13차 국제 회의, COCOON 2007년, 밴프 캐나다, 7월 16-19, 2007, 회보, 강의 노트 컴퓨터 과학으로, 4598 vol., Springer-Verlag,를 대신하여 서명함. 243–253, CiteSeerX 10.1.1.483.874,. doi:10.1007/978-3-540-73545-8_25, 아이 에스비엔 978-3-540-73544-1.
  3. ^ a b 를 클릭합니다Gross, Jonathan; Tucker, Thomas W. (2001), Topological Graph Theory, Dover Publications, ISBN 978-0-486-41741-7.
  4. ^ 를 클릭합니다Lando, Sergei K.; Zvonkin, Alexander K. (2004), Graphs on Surfaces and their Applications, Springer-Verlag, ISBN 978-3-540-00203-1.
  5. ^ 를 클릭합니다Mutzel, Petra; Weiskircher, René (2000), "Computing Optimal Embeddings for Planar Graphs", Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1858, Springer-Verlag, pp. 95–104, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.
  6. ^ 를 클릭합니다Didjev, Hristo N. (1995), "On drawing a graph convexly in the plane", Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer-Verlag, pp. 76–83, doi:10.1007/3-540-58950-3_358, ISBN 978-3-540-58950-1.
  7. ^ Duncan, 크리스티안, 굿리치, 마이클 T.;Kobourov, 스티븐(2010년),"평면 설계 도면 Higher-Genus Graphs의"Graph도면, 17일 국제 심포지엄, 승무원 2009년, 시카고, 일리노이 주, 미국, 9월 22-25인 2009년 수정된 논문, 강의 노트 컴퓨터 과학으로, 5849 vol., Springer-Verlag,를 대신하여 서명함. 45–56, arXiv:0908.1608, doi:10.1007/978-3-642-11805-0_7, 아이 에스비엔 9.78-3-642-11804-3.
  8. ^ Thomassen, Carsten (1989), "The graph genus problem is NP-complete", Journal of Algorithms, 10 (4): 568–576, doi:10.1016/0196-6774(89)90006-0
  9. ^ 를 클릭합니다Filotti, I. S.; Miller, Gary L.; Reif, John (1979), "On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)", Proc. 11th Annu. ACM Symposium on Theory of Computing, pp. 27–37, doi:10.1145/800135.804395.
  10. ^ Myrvold, Wendy; Kocay, William (March 1, 2011). "Errors in Graph Embedding Algorithms". Journal of Computer and System Sciences. 2 (77): 430–438. doi:10.1016/j.jcss.2010.06.002.
  11. ^ Mohar, Bojan (1999), "A linear time algorithm for embedding graphs in an arbitrary surface", SIAM Journal on Discrete Mathematics, 12 (1): 6–26, CiteSeerX 10.1.1.97.9588, doi:10.1137/S089548019529248X