사각그래프

Squaregraph
네모그래프.

수학의 한 가지인 그래프 이론에서 사각형 그래프는 모든 경계면이 사방형이고 이웃이 3개 이하인 모든 꼭지점이 한없는 얼굴에 입사하는 방식으로 평면에 그려질 수 있는 비방향 그래프의 일종이다.

관련 그래프 클래스

사각형 그래프에는 특수 사례 나무, 격자 그래프, 기어 그래프, 폴리모노 그래프 등이 포함된다.

평면 그래프가 될 뿐만 아니라 사각형 그래프는 중위수 그래프로서, 3개의 꼭지점 쌍 사이에 최단 경로에 있는 고유한 중위수 꼭지점 m(u,v,w)이 있다는 것을 의미한다.[1]중위수 그래프의 경우 보다 일반적으로 사각형 그래프는 부분 큐브도 된다. 사각형 그래프의 정점은 2진수 문자열로 라벨을 붙여 문자열 사이의 해밍 거리가 정점 사이의 최단 경로 거리와 동일하도록 할 수 있다.

사각형 그래프에서 각 구역(사면측정감시 평행 가장자리의 등가 등급)과 사각형에서 만나는 각 두 구역에 대한 에지를 만들어 얻은 그래프는 단위 디스크의 삼각형 없는 화음 다이어그램에 의해 결정되는 원 그래프다.[2]

특성화

사각형 그래프는 평면 임베딩 이외의 여러 가지 방법으로 특성화할 수 있다.[2]

  • 그것들은 유도 하위그래프로 금지된 그래프의 무한대 멤버를 포함하지 않는 중위수 그래프들이다.이러한 금지된 그래프는 큐브(K의3 심플렉스 그래프), 가장자리와 집게 K의1,3 데카르트 산물(클로의 심플렉스 그래프), 그리고 바퀴의 허브에 연결된 정점 하나를 더 추가함으로써 기어 그래프에서 형성된 그래프(단독 정점을 가진 사이클의 분리 결합을 보여주는 심플렉스 그래프)이다.
  • 이러한 그래프는 연결되고 양립되는 그래프로서, (임의 정점 r을 루트로 선택한 경우) 모든 정점에는 r에 더 가까운 최대 두 개의 이웃이 있고, 따라서 모든 정점 v에서 v(각 에지 사건에 대한 정점을 v에, 그리고 v를 포함하는 각 4 사이클에 대한 에지를 가진 그래프)의 링크는 3개 이상의 주기 중 하나이다.길의 결합을 해제할 수도 있어.
  • 이 그래프는 세 개의 상호 교차선이 없는 쌍곡면의 선 배열의 이중 그래프다.

알고리즘

제곱그래프의 특성화는 임의 그래프의 평면성 테스트에 더 복잡한 선형 시간 알고리즘을 사용할 필요 없이, 주어진 그래프가 사각형인지 여부를 테스트하기 위한 선형 시간 알고리즘의 일부로서 넓이 첫 번째 검색과 함께 사용할 수 있다.[2]

squaregraphs에 대한 여러 알고리즘 문제 더 효율적으로 더 일반적인 평면 또는 평균 그래프보다. 예를 들면, Chepoi, 드라간 &, squaregraphs의 직경을 계산, 그리고 꼭지점에 최대 거리 최소화하면서 발견을 위해 Vaxès(2002년)과 Chepoi, Fanciullini&Vaxès(2004년)현재 선형 시간 알고리즘을 계산할 수 있다. 모든 other 정점

메모들

  1. ^ 솔탄, 잠비츠키 & 프리슈카루(1973년).평면 중위수 그래프에 대한 자세한 내용은 Peterin(2006)을 참조하십시오.
  2. ^ a b c 반델트, 체포이 & 엡스타인(2010년).

참조

  • Bandelt, Hans-Jürgen; Chepoi, Victor; Eppstein, David (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301, S2CID 10788524.
  • Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), "Center and diameter problem in planar quadrangulations and triangulations", Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 346–355.
  • Chepoi, Victor; Fanciullini, Clémentine; Vaxès, Yann (2004), "Median problem in some plane triangulations and quadrangulations", Computational Geometry, 27 (3): 193–210, doi:10.1016/j.comgeo.2003.11.002.
  • Peterin, Iztok (2006), "A characterization of planar median graphs", Discussiones Mathematicae Graph Theory, 26 (1): 41–48, doi:10.7151/dmgt.1299
  • Soltan, P.; Zambitskii, D.; Prisǎcaru, C. (1973), Extremal Problems on Graphs and Algorithms of their Solution (in Russian), Chişinǎu, Moldova: Ştiinţa.