지도 그래프

Map graph
평면 내 8개 영역(좌측 하단)의 모서리에 인접하여 정의되는 칵테일 파티2,2,2,2 그래프K 또는 평면 양분 그래프(우측 하단, 롬빅 도데카헤드론의 그래프)
미국의 Four Corners. 이 네 개의 주가 한 지점에서 만나더라도, 0이 아닌 길이의 경계를 공유하기보다는, 해당 지도 그래프에서 인접 정점을 형성한다.
왕의 그래프, 체스판의 사각형 지도 그래프.체스 킹은 이 그래프의 두 정점 사이를 이동할 수 있다.

수학의 한 분야인 그래프 이론에서 지도 그래프는 유클리드 평면의 단순하게 연결되고 내부적으로 분리된 많은 부분의 교차 그래프로 형성된 비방향 그래프다.지도 그래프에는 평면 그래프가 포함되지만 더 일반적이다.어떤 지역이라도 공통의 구석에서 만날 수 있으며(4개의 주가 만나는 미국의 포코너스에서처럼), 지도 그래프를 할 때 가장 큰 집단이 정점 4개만 있는 평면 그래프와는 달리 해당 정점을 연결하는 정점을 포함하는 정점을 포함한다.[1]지도 그래프의 또 다른 예는 체스왕이 움직일 수 있는 정사각형 쌍을 연결하는 체스판의 사각형을 보여주는 지도 그래프인 왕의 그래프다.

조합 표현

지도 그래프를 조합하여 "평면 쌍방향 그래프의 절반 제곱"으로 나타낼 수 있다.즉, G = (U,V,E)를 양분(U,V)과 함께 평면적 양분 그래프로 한다.G의 제곱은 동일한 꼭지점 집합에 있는 또 다른 그래프인데, 두 꼭지점이 G에서 최대 두 단계 떨어져 있을 때 사각형에 인접해 있다.반제곱 또는 양분 반은 사각형 그래프에서 양분(예: V)의 한 쪽의 유도 하위 그래프로서, 정점 세트는 V이며, V의 두 꼭지점 사이에 가장자리가 있으며, 두 단계 떨어져 있다.반제곱은 지도 그래프다.G의 평면 내장을 찾고, V와 그 인접 가장자리의 각 정점을 별 모양 영역으로 확장하여 기하학적으로 표현할 수 있어, 이러한 영역이 U의 정점에 닿도록 한다. 반대로 모든 지도 그래프는 이런 식으로 반제곱으로 나타낼 수 있다.[1]

계산 복잡성

1998년, Mikkel Thorup은 지도 그래프는 다항식 시간에 인식될 수 있다고 주장했다.[2]그러나 그가 스케치한 알고리즘의 높은 지수는 그것을 비실용적으로 만들고, 소럽은 그의 방법과 그 증거에 대한 자세한 내용은 발표하지 않았다.[3]

최대 독립형 집합 문제는 지도 그래프에 대한 다항식 시간 근사 체계를 가지고 있으며, 색도 수는 다항식 시간에서 2의 요인 내에 근사치를 구할 수 있다.[4]비등력 이론은 지도 그래프의 최적화 문제를 위한 많은 다른 근사 알고리즘과 고정 매개변수 추적 가능한 알고리즘으로 이어진다.[5][6][7]

다양성 및 관련 개념

k-map 그래프는 대부분의 k 지역이 어느 지점에서 만나는 지역 집합에서 파생된 지도 그래프다.동등하게, 이것은 정점 집합 U(반정사각형을 유도하는 데 사용되지 않는 양정점 측면)가 최대 k를 갖는 평면 쌍정점 그래프의 반정사각형이다.3맵 그래프는 평면 그래프로, 모든 평면 그래프는 3맵 그래프로 나타낼 수 있다.모든 4맵 그래프는 1평형 그래프, 가장자리당 최대 1개의 교차로를 사용하여 그릴 수 있는 그래프, 모든 최적 1평형 그래프(각방면마다 교차 대각선 2개를 추가하여 평면 사각형으로 형성된 그래프)는 4맵 그래프다.그러나 (지도 그래프와 달리) 지도 그래프에는 4Vx 완전 하위 그래프의 일부가 아닌 교차 가장자리가 포함되기 때문에 일부 다른 1-평면 그래프는 지도 그래프가 아니다.[1]

참조

  1. ^ a b c 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.
  2. ^ Thorup, Mikkel (1998), "Map graphs in polynomial time", Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 396–405, doi:10.1109/SFCS.1998.743490, ISBN 978-0-8186-9172-0.
  3. ^ Brandenburg, Franz J. (August 2018), "Characterizing and Recognizing 4-Map Graphs", Algorithmica, doi:10.1007/s00453-018-0510-x
  4. ^ Chen, Zhi-Zhong (2001), "Approximation algorithms for independent sets in map graphs", Journal of Algorithms, 41 (1): 20–40, doi:10.1006/jagm.2001.1178, MR 1855346.
  5. ^ Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammadtaghi; Thilikos, Dimitrios M. (2005), "Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs", ACM Transactions on Algorithms, 1 (1): 33–47, CiteSeerX 10.1.1.113.2070, doi:10.1145/1077464.1077468, MR 2163129.
  6. ^ Demaine, Erik D.; Hajiaghayi, Mohammadtaghi (2007), "The Bidimensionality Theory and Its Algorithmic Applications", The Computer Journal, 51 (3): 292–302, doi:10.1093/comjnl/bxm033, hdl:1721.1/33090.
  7. ^ Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket (2012), "Bidimensionality and geometric graphs", Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1563–1575, arXiv:1107.2221, doi:10.1137/1.9781611973099.124, ISBN 978-1-61197-210-8, MR 3205314.