두께(그래프 이론)

Thickness (graph theory)

그래프 이론에서 그래프 G의 두께는 G의 가장자리를 분할할 수 있는 평면 그래프의 최소 수입니다.즉, 모두 동일한 정점 집합을 가진 k 평면 그래프의 조합이 G인 경우 G의 두께는 최대 k이다.[1][2]즉, 그래프의 두께는 조합이 그래프 G와 동일한 평면 하위 그래프의 최소 수입니다.[3]

따라서 평면 그래프는 두께 1. 두께 2의 그래프를 biplanar 그래프라고 한다.두께의 개념은 1962년 프랭크 하라리의 추측에서 비롯된다.9개 점의 그래프의 경우, 자체 또는 그 보완 그래프는 평면이 아니다.문제는 전체 그래프 K가9 바이플라나(그렇지 않고, 추측이 사실)인지를 판단하는 것과 같다.[4]1998년 현재 이 화제의 예술 상태에 대한 종합적인[3] 조사는 페트라 무첼, 토마스 오덴탈, 마크 샤브롯에 의해 작성되었다.[5]

특정 그래프

n 꼭지점 K에 대한 전체n 그래프의 K는

두께가 3인 경우 n = 9, 10인 경우는 제외한다.[6][7]

일부 예외를 제외하고 완전한 초당적 그래프 K의a,b 두께는 일반적으로 다음과 같다.[8][9]

관련 문제

모든 숲은 평면이며, 모든 평면 그래프는 최대 3개의 숲으로 분할할 수 있다.따라서 어떤 그래프 G의 두께는 최소한 같은 그래프(분할할 수 있는 숲의 최소 수)의 수목성과 같으며 적어도 3으로 나눈 수목성과 같다.[2][10]또한 G의 두께는 다른 표준 그래프 불변성의 상수인자, 즉 G의 최대 초과 서브그래프로 정의되는 변질성, 서브그래프 내의 최소도 내에 있다.n-vertex 그래프에 두께 t가 있으면 최대 t(3n - 6) 에지가 있어야 하며, 여기서부터 그 변질도는 최대 6t - 1이다.다른 방향에서, 만약 그래프가 퇴보성 D를 가지고 있다면, 그래프는 최대 D에서 수목성과 두께를 가진다.

두께는 동시 임베딩 문제와 밀접한 관련이 있다.[11]둘 이상의 평면 그래프가 모두 동일한 정점 세트를 공유하는 경우, 가장자리가 곡선으로 그려진 평면에 이 모든 그래프를 삽입하여 각 정점이 다른 모든 도면에서 동일한 위치를 갖도록 할 수 있다.단, 직선 세그먼트로 그려진 가장자리를 유지하면서 이러한 도면을 구성할 수는 없을 수 있다.

다른 그래프 불변성 그래프, 즉 그래프 G의 직선 두께 또는 기하학적 두께는 G가 분해될 수 있는 평면 그래프의 최소 개수를 계산하는데, 이 그래프들은 모두 직선 가장자리와 동시에 그릴 수 있다는 제한에 따라 계산된다.책 두께는 추가 제약을 추가하며, 모든 정점을 볼록한 위치로 그려서 그래프의 원형 레이아웃을 형성한다.그러나, 수목성과 퇴보성의 상황과 대조적으로, 이 세 가지 두께 매개변수 중 두 가지는 항상 서로 일정한 요소 안에 있지 않다.[12]

계산 복잡성

주어진 그래프의 두께를 계산하는 것은 NP-힘이고, 두께가 최대 2인지 여부를 테스트하는 것은 NP-완전이다.[13]그러나 수목성에 연결하면 다항 시간에서 3의 근사비 내에서 두께를 근사치로 추정할 수 있다.

참조

  1. ^ Tutte, W. T. (1963), "The thickness of a graph", Indag. Math., 25: 567–577, MR 0157372.
  2. ^ a b Mutzel, Petra; Odenthal, Thomas; Scharbrodt, Mark (1998), "The thickness of graphs: a survey", Graphs and Combinatorics, 14 (1): 59–73, doi:10.1007/PL00007219, MR 1617664.
  3. ^ a b 크리스천 A.Duncan, On Graph Thickness, 기하학적 두께 및 분리자 이론, CCCG 2009, 밴쿠버, BC, 2009년 8월 17~19일
  4. ^ Mäkinen, Erkki; Poranen, Timo (2012). "An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph". Missouri J. Math. Sci. 24 (1): 76–87.
  5. ^ 페트라 무첼, 토마스 오덴탈, 마크 샤브로트, 그래프의 두께: 설문 조사
  6. ^ 무첼, 오덴탈 & 샤르브로트(1998), 정리 3.2.
  7. ^ Alekseev, V. B.; Gončakov, V. S. (1976), "The thickness of an arbitrary complete graph", Mat. Sb., New Series, 101 (143): 212–230, MR 0460162.
  8. ^ 무첼, 오덴탈 & 샤르브로트(1998), 정리 3.4.
  9. ^ Beineke, Lowell W.; Harary, Frank; Moon, John W. (1964), "On the thickness of the complete bipartite graph", Proc. Cambridge Philos. Soc., 60: 1–5, doi:10.1017/s0305004100037385, MR 0158388.
  10. ^ Dean, Alice M.; Hutchinson, Joan P.; Scheinerman, Edward R. (1991), "On the thickness and arboricity of a graph", Journal of Combinatorial Theory, Series B, 52 (1): 147–151, doi:10.1016/0095-8956(91)90100-X, MR 1109429.
  11. ^ Brass, Peter; Cenek, Eowyn; Duncan, Cristian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna; Mitchell, Joseph S. B. (2007), "On simultaneous planar graph embeddings", Computational Geometry, 36 (2): 117–130, doi:10.1016/j.comgeo.2006.05.006, MR 2278011.
  12. ^ Eppstein, David (2004), "Separating thickness from geometric thickness", Towards a theory of geometric graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, pp. 75–86, arXiv:math/0204252, doi:10.1090/conm/342/06132, MR 2065254.
  13. ^ Mansfield, Anthony (1983), "Determining the thickness of graphs is NP-hard", Mathematical Proceedings of the Cambridge Philosophical Society, 93 (1): 9–23, doi:10.1017/S030500410006028X, MR 0684270.