1평형 그래프

1-planar graph
히우드 그래프의 1평형 도면: 가장자리 중 6개는 단일 교차하며 나머지 15개는 교차하지 않는다.

위상 그래프 이론에서 1-평면 그래프유클리드 평면에서 가장자리가 하나의 교차점을 가지도록 그려질 수 있는 그래프로, 하나의 추가 가장자리를 교차한다. 평면 그래프의 가장 자연스러운 일반화 중 하나인 1평면 그래프를 그런 식으로 그리면 도면을 1평면 그래프 또는 1평면 내장 그래프라고 한다.

컬러링

1평형 그래프는 링겔(1965)에 의해 처음 연구되었는데, 링겔은 최대 7가지 색으로 색칠할 수 있다는 것을 보여주었다.[1] 나중에, 최악의 경우, 이러한 그래프에 색을 칠하는 데 필요한 정확한 색상 수는 6개로 나타났다.[2] 전체 그래프 K6 예인 1-평면도를 보면 1-평면 그래프는 때때로 6가지 색상이 필요할 수 있다. 그러나 여섯 가지 색이면 언제나 충분하다는 증거는 더욱 복잡하다.

삼각 프리즘 그래프의 꼭지점과 면에 색칠을 하려면 6가지 색상이 필요하다.

링겔의 동기는 평면 그래프총색상의 변동을 해결하기 위해 노력했는데, 평면 그래프의 정점과 면에 동일한 색상을 가진 두 정점이 없고, 인접한 두 정점이 동일한 색상을 가지지 않으며, 서로 인접한 정점과 얼굴이 동일한 색상을 가지지 않도록 동시에 색칠하는 것이었다.이것은 분명히 주어진 그래프에 4가지정리를 적용하고 4가지 색상의 2개의 디스조인트 세트를 사용하여 8가지 색상으로 할 수 있다. 단, 주어진 평면 그래프의 정점이나 면에 정점이 있고, 두 개의 보조 그래프 정점이 주어진 평면 그래프의 인접 형상에 해당할 때마다 인접하는 보조 그래프를 형성하여 더 적은 색상을 얻을 수 있다. 보조 그래프의 정점 색상은 원래 평면 그래프의 정점 면 색상에 해당한다. 이 보조 그래프는 1-평면으로, 링겔의 정점-얼굴 색소 문제도 6가지 색상으로 해결할 수 있다.[2] 그래프 K6 이런 식으로 보조 그래프로 형성될 수는 없지만 그럼에도 불구하고 정점-얼굴 색채 문제 역시 6가지 색상을 필요로 한다. 예를 들어 평면 그래프가 삼각 프리즘이라면 그 11가지 정점과 면은 6가지 색상을 필요로 하는데, 그 중 3가지 색상은 한 가지 색상을 부여할 수 없기 때문이다.[3]

모서리 밀도

정점이 n개인 1평형 그래프마다 최대 4n - 8개의 가장자리가 있다.[4] 더 강하게 말하면, 각 1-평면 도면은 최대 n - 2개의 교차점을 가지고 있다. 각 교차하는 가장자리 쌍에서 하나의 가장자리를 제거하면 평면 그래프가 남는다. 평면 그래프는 최대 3n - 6개의 가장자리를 가질 수 있으며, 이 경우 원래 1-평면 그래프의 가장자리 수에 대한 4n - 8의 경계가 바로 뒤따른다.[5] 단, 평면 그래프(특정 꼭지 집합의 모든 최대 평면 그래프는 서로 동일한 수의 가장자리를 갖는 그래프)와 달리 4n - 8 에지보다 훨씬 적은 최대 1 평면 그래프(1-평도를 보존하면서 추가 가장자리를 추가할 수 없는 그래프)가 존재한다.[6] 1-평면 그래프의 가능한 최대 에지 수에 대한 4n - 8의 경계는 이 그래프는 21개의 에지를 가지고 있고7 이 경우 4n - 8 = 20 < 21이기 때문에 7개의 꼭지점에 대한 전체 그래프 K가 1-평면이 아님을 보여주는 데 사용될 수 있다.[7]

1평형 그래프는 최대 가능한 4n - 8개의 가장자리가 정확히 있으면 최적의 1평형 그래프라고 한다. 최적의 1-평형 그래프를 포함하는 1-평형 그래프에서 교차되지 않은 가장자리는 반드시 사분면(모든 면이 사분면다면 그래프)을 형성한다. 모든 사분면은 이러한 방식으로 최적의 1-평면 그래프를 생성하는데, 각 사분면에 대각선 두 개를 더하면 된다. 따라서 모든 최적 1-평면 그래프는 오일리언(모든 정점에는 짝수도가 있음)이고, 그러한 그래프의 최소도는 6이며, 모든 최적 1-평면 그래프는 정확히 6의 정점 이상을 8개 이상 가진다. 또한 모든 최적 1-평면 그래프는 4-Vertex 연결되며, 이러한 그래프에서 4-Vertex가 절단될 때마다 기저 사각형의 분리 사이클이 된다.[8]

직선 1-평면도(즉, 각 가장자리가 선 세그먼트로 표현되고 각 선 세그먼트가 다른 가장자리로 교차되는 도면)가 있는 그래프들은 무한히 많은 그래프에 의해 달성되는 최대 가장자리 수에 대해 4n - 9의 약간 더 엄격한 경계를 가진다.[9]

전체 다중 사이트 그래프

칵테일 파티 그래프K2,2,2,2 1평면 도면

1-평면 전체 그래프, 전체 쌍방향 그래프 및 보다 일반적으로 완전한 다중 표준 그래프의 완전한 분류가 알려져 있다. K형식2,n 모든 완전한 초당적 그래프는 K형식1,1,n 모든 완전한 삼분법 그래프와 마찬가지로 1-평면이다. 이러한 무한대의 예시 집합 외에 K6, K1,1,1,6, K, K1,1,2,32,2,2,2, K1,1,1,2,2, K, 그리고 그 하위 그래프들만이 완전한 다분점 1-평면 그래프들이다. 1평면이 아닌 최소 다중분포 그래프는 K3,7, K, K4,5, K1,3,4, K이다2,3,31,1,1,1,3. 예를 들어 완전한 초당적 그래프 K3,6 K1,1,1,6 하위그래프이기 때문에 1행성이지만 K3,7 1행성이 아니다.[7]

계산 복잡성

주어진 그래프가 1-평면인지 여부를 검정하는 것이 NP-완전하며,[10][11] 단 하나의 에지를[12] 추가하여 평면 그래프로 형성된 그래프와 경계 대역폭의 그래프에 대해서도 NP-완전성을 유지한다.[13] 문제는 사이클로메틱 수나무 깊이로 매개변수를 지정했을 때 고정 매개변수를 추적할 수 있으므로, 그러한 매개변수가 경계인 다항 시간 내에 해결할 수 있다.[13]

파리의 평면 그래프 정리와는 대조적으로 모든 1-평면 그래프를 가장자리에 대해 직선 세그먼트로 1-평면으로 그릴 수는 없다.[14][15] 단, 1-평면 도면이 이러한 방식으로 직선화될 수 있는지 여부는 다항식 시간에 시험할 수 있다.[16] 또한 모든 3개의 버텍스로 연결된 1-평면 그래프는 1-평면 도면을 가지고 있으며, 이 도면의 바깥 면에 있는 최대 한 모서리에 굴곡이 있다. 이 도면은 그래프를 1평면으로 내장한 상태에서 선형 시간으로 제작할 수 있다.[17] 1행 그래프는 책의 두께를 경계로 하고 있지만 [18]K2,2,2,2 포함한 일부 1행 그래프는 책 두께가 최소 4개 이상이다.[19]

1-평면 그래프는 로컬 트리 너비에 경계를 두었는데, 이는 직경의 1-평면 그래프가 최대 f(d)에서 트리 너비를 갖는 것과 같은 (선형) 함수가 있다는 것을 의미한다. 동일한 속성은 경계된 속(edge당 교차 수)의 경계된 속(bounded)의 표면에 삽입될 수 있는 그래프에 대해 보다 일반적인 의미를 갖는다. 그들은 또한 분리기를 가지고 있는데, 제거된 정점의 작은 집합은 그래프를 전체 그래프 크기의 일정한 부분인 연결된 구성요소로 분해한다. 이러한 특성에 기초하여 베이커의 근사 알고리즘 설계 기법 등 평면 그래프의 수많은 알고리즘을 1 평면 그래프로 확장할 수 있다. 예를 들어, 이 방법은 1-평면 그래프의 최대 독립 집합에 대한 다항식 시간 근사 설계로 이어진다.[20]

일반화 및 관련 개념

1-행성에 대한 외부 평면 그래프와 유사한 그래프의 클래스를 외부 1-행성 그래프라고 한다. 이것들은 디스크의 경계에 정점이 있고 에지당 교차점이 최대 한 개씩 있는 디스크에 그려질 수 있는 그래프들이다. 이러한 그래프는 항상 직선 가장자리와 직각 교차점으로 그릴 수 있다.[21] 주어진 그래프의 SPQR 트리에서 동적 프로그래밍을 사용하면 외측 1-평형인지 선형 시간대에 테스트할 수 있다.[22][23] 그래프의 트리코넥트 구성 요소(SPQR 트리의 노드)는 사이클 그래프, 본드 그래프 및 4Vertex 전체 그래프로만 구성될 수 있으며, 이 그래프에서 외부 1-평면 그래프는 평면이며 최대 3개의 트리 너비가 있다는 것을 확인할 수 있다.

1-평면 그래프는 4-지도 그래프를 포함하며, 평면에 있는 지역의 인접성에서 형성된 그래프를 포함하며, 어느 지점에서든 4개의 지역이 만난다. 반대로 모든 최적 1-평면 그래프는 4-지도 그래프다. 그러나 최적의 1-평면이 아닌 1-평면 그래프는 지도 그래프가 아닐 수 있다.[24]

1-평면 그래프는 k-평면 그래프로 일반화되었으며, 각 모서리가 최대 k-k 간격으로 교차되는 그래프(0-평면 그래프는 정확히 평면 그래프임). 링겔은 G국부 교차 숫자를 최소 음수가 아닌 정수 k로 정의하여 G가 k-평면도를 갖도록 하였다. 국부 교차번호는 최적 도면의 가장자리에 대한 교차 그래프의 최대 정도이며 두께(가장자리를 분할할 수 있는 평면 그래프의 최소 개수)는 적절한 도면의 교차 그래프의 색수로 볼 수 있기 때문에 브룩스의 정리에서는 두께가 다음과 같이 된다. 지역 건널목 번호에 최대 1을 더하면 된다.[25] 정점이 n개인 k-planar 그래프에는 최대 O(kn1/2) 에지와 트리 너비 O(kn)1/2[27]가 있다.[26] 깊이가 d인 k-planar 그래프의 얕은 부차는 그 자체로 (2d + 1)k-planar 그래프이기 때문에 1-planar 그래프와 k-planar 그래프의 얕은 부차 역시 희소 그래프로서 1-planar 그래프와 k-planar 그래프의 경계가 확장되었음을 시사한다.[28]

비 평면 그래프는 그래프 도면에서 교차하는 최소 에지 쌍의 교차 번호에 의해 매개변수화될 수도 있다. 교차 번호 k가 있는 그래프는 반드시 k-planar이지만, 그 반대도 반드시 k-planar일 필요는 없다. 예를 들어, Heawood 그래프는 3번 교차점을 가지고 있지만, 3번의 교차점이 모두 그래프의 같은 가장자리에서 발생할 필요는 없기 때문에, 1-평면이며, 사실상 총 교차 횟수와 엣지당 교차 횟수를 동시에 최적화하는 방법으로 그릴 수 있다.

비 평면 그래프의 또 다른 관련 개념은 그래프 왜도인데, 이것은 그래프 평면도를 만들기 위해 제거해야 하는 최소 에지 수입니다.

참조

  1. ^ Ringel, Gerhard (1965), "Ein Sechsfarbenproblem auf der Kugel", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (in German), 29 (1–2): 107–117, doi:10.1007/BF02996313, MR 0187232, S2CID 123286264.
  2. ^ Jump up to: a b Borodin, O. V. (1984), "Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs", Metody Diskretnogo Analiza (41): 12–26, 108, MR 0832128.
  3. ^ Albertson, Michael O.; Mohar, Bojan (2006), "Coloring vertices and faces of locally planar graphs" (PDF), Graphs and Combinatorics, 22 (3): 289–295, doi:10.1007/s00373-006-0653-4, MR 2264852, S2CID 1028234.
  4. ^ Schumacher, H. (1986), "Zur Struktur 1-planarer Graphen", Mathematische Nachrichten (in German), 125: 291–300, doi:10.1002/mana.19861250122, MR 0847368.
  5. ^ Czap, Július; Hudák, Dávid (2013), "On drawings and decompositions of 1-planar graphs", Electronic Journal of Combinatorics, 20 (2), P54, doi:10.37236/2392.
  6. ^ Brandenburg, Franz Josef; Eppstein, David; Gleißner, Andreas; Goodrich, Michael T.; Hanauer, Kathrin; Reislhuber, Josef (2013), "On the density of maximal 1-planar graphs", in Didimo, Walter; Patrignani, Maurizio (eds.), Proc. 20th Int. Symp. Graph Drawing.
  7. ^ Jump up to: a b Czap, Július; Hudák, Dávid (2012), "1-planarity of complete multipartite graphs", Discrete Applied Mathematics, 160 (4–5): 505–512, doi:10.1016/j.dam.2011.11.014, MR 2876333.
  8. ^ Suzuki, Yusuke (2010), "Re-embeddings of maximum 1-planar graphs", SIAM Journal on Discrete Mathematics, 24 (4): 1527–1540, doi:10.1137/090746835, MR 2746706.
  9. ^ Didimo, Walter (2013), "Density of straight-line 1-planar graph drawings", Information Processing Letters, 113 (7): 236–240, doi:10.1016/j.ipl.2013.01.013, MR 3017985.
  10. ^ Grigoriev, Alexander; Bodlaender, Hans L. (2007), "Algorithms for graphs embeddable with few crossings per edge", Algorithmica, 49 (1): 1–11, doi:10.1007/s00453-007-0010-x, hdl:1874/17980, MR 2344391, S2CID 8174422.
  11. ^ Korzhik, 블라디미르 P.;Mohar, 보얀(2009년),"1-immersions을 극미한 장애물과 1-planarity 시험의 경도", Tollis, 요안 니스 G단조, Patrignani, 마우리치오(eds.)Graph도면:16일 국제 심포지엄, 승무원 명단과 2008년, 이라클리오, 그리스 크레테 섬, 9월 21일부터 24일까지, 2008년, 수정된 논문, 강의 노트 컴퓨터 과학으로, 5417, 스프링거,를 대신하여 서명함. 302–312, arXiv:1110.4881., doi:10.1007/978-3-642-00219-9_29, S2CID 13436158.
  12. ^ Cabello, Sergio; Mohar, Bojan (2012), Adding one edge to planar graphs makes crossing number and 1-planarity hard, arXiv:1203.5944, Bibcode:2012arXiv1203.5944C. 2010년 제17회 ACM 컴퓨터 기하학 심포지엄에서 논문의 확대판.
  13. ^ Jump up to: a b Bannister, Michael J.; Cabello, Sergio; Eppstein, David (2013), "Parameterized complexity of 1-planarity", Algorithms and Data Structures Symposium (WADS 2013), arXiv:1304.5591, Bibcode:2013arXiv1304.5591B, doi:10.7155/jgaa.00457, S2CID 4417962.
  14. ^ Eggleton, Roger B. (1986), "Rectilinear drawings of graphs", Utilitas Mathematica, 29: 149–172, MR 0846198.
  15. ^ Thomassen, Carsten (1988), "Rectilinear drawings of graphs", Journal of Graph Theory, 12 (3): 335–341, doi:10.1002/jgt.3190120306, MR 0956195.
  16. ^ 홍 Seok-Hee, Eades, 피터, 리오타, 주세페;Poon, Sheung-Hung(2012년),"1-planar 그래프에 Fáry의 정리", Gudmundsson, 요아힘;Mestre, 훌리 안은;Viglas, Taso(eds.), 컴퓨팅과 조합론:18일 연간 국제 회의, COCOON 2012년 시드니, 호주, 8월 등 2012년, 회보, 강의 노트 컴퓨터 과학으로, 7434, 파.링거,를 대신하여 서명함. 335–346, doi:10.1007/978-3-642-32241-9_29.
  17. ^ Alam, Md. Jawaherul; Brandenburg, Franz J.; Kobourov, Stephen G. (2013), "Straight-line grid drawings of 3-connected 1-planar graphs", Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers (PDF), Lecture Notes in Computer Science, 8242, pp. 83–94, doi:10.1007/978-3-319-03841-4_8.
  18. ^ Bekos, Michael A.; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), "1-Planar graphs have constant book thickness", Algorithms – ESA 2015, Lecture Notes in Computer Science, 9294, Springer, pp. 130–141, doi:10.1007/978-3-662-48350-3_12.
  19. ^ Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113–125.
  20. ^ 그리고리예프 & 보들라엔더(2007년). 그리고리예프와 보들라엔더는 알려진 1개의 평면 임베딩이 있는 그래프에 대해서만 결과를 진술하고, 4개의 정점으로 대체된 교차점 임베딩의 평면화의 트리 분해를 사용하지만, 그들의 방법은 직접적으로 원래의 1 평면 그래프의 국부적인 나무 너비를 암시하여 베이커의 방법이 적용될 수 있게 한다. 내장을 알지 못한 채 직접 연결했어
  21. ^ Dehkordi, Hooman Reisi; Eades, Peter (2012), "Every outer-1-plane graph has a right angle crossing drawing", International Journal of Computational Geometry & Applications, 22 (6): 543–557, doi:10.1142/S021819591250015X, MR 3042921.
  22. ^ 홍 Seok-Hee, Eades, 피터는 세련되지는 Katoh, 나오키, 리오타, 주세페, 슈바이처, 파스칼, 스즈키, 유수케(2013년),"outer-1-planarity을 시험하기 위한linear-time 알고리즘", Wismath, Stephen은, 볼프, 알렉산더(eds.), 21일 국제 심포지엄, 승무원 2013년, 보르도, 프랑스, 9월 23일부터 25일까지, 2013년 선택 기술, 강의 노트 컴퓨터 과학으로, 8합치하도록 수정되었다.242개,를 대신하여 서명함. 71–82, doi:10.1007/978-3-319-03841-4_7.
  23. ^ 아우어, 크리스토퍼, Bachmaier, 크리스티안, 브란덴부르크, 프란츠 J.;Gleißner, 안드레아스, 하나워, Kathrin, 뉴워스, 다니엘;Reislhuber, 요제프(2013년),"선형 시간에 외부1-planar 그래프를 파악하는 것.", Wismath, Stephen은, 볼프, 알렉산더(eds.), 21일 국제 심포지엄, 승무원 2013년, 보르도, 프랑스, 9월 23일부터 25일까지, 2013년 선택 기술, L. 수정Ecture 메모 컴퓨터 과학, 8242,를 대신하여 서명함에서. 107–118, doi:10.1007/978-3-319-03841-4_10.
  24. ^ Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM, 49 (2): 127–138, arXiv:cs/9910013, doi:10.1145/506147.506148, MR 2147819, S2CID 2657838.
  25. ^ Kainen, Paul (1973), "Thickness and coarseness of graphs", Abh. Math. Sem. Univ. Hamburg, 39: 88–95, doi:10.1007/BF02992822, MR 0335322, S2CID 121667358.
  26. ^ Pach, János; Tóth, Géza (1997), "Graphs drawn with few crossings per edge", Combinatorica, 17 (3): 427–439, doi:10.1007/BF01215922, MR 1606052, S2CID 20480170.
  27. ^ Dujmović, Vida; Eppstein, David; Wood, David R. (2015), "Genus, treewidth, and local crossing number", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 77–88, arXiv:1506.04380, Bibcode:2015arXiv150604380D.
  28. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, 28, Springer, Theorem 14.4, p. 321, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.

추가 읽기