평면화

Planarization

그래프 도면에서 평면화는 대형 평면 그래프에 비 평면 그래프를 포함시켜 평면 그래프가 아닌 그래프로 도면 방법을 확장하는 방법이다.[1][2]

임의의 방법을 사용하여 주어진 그래프에 대한 도면(교차 포함)을 찾은 다음, 각 교차점을 새로운 인공 정점으로 교체하여 각 교차점을 경로로 세분화하도록 하는 방법으로 평면화를 수행할 수 있다.원래의 그래프는 평면화의 몰입도 단조로 표현될 것이다.

증분 평면화에서 평면화 과정은 두 단계로 나뉜다.첫째, 주어진 그래프 안에서 큰 평면 하위 그래프가 발견된다.그런 다음, 이 하위 그래프의 일부가 아닌 나머지 가장자리는 한 번에 하나씩 다시 추가되고 평면 하위 그래프의 내장을 통해 라우팅된다.이들 가장자리 중 하나가 이미 임베딩된 가장자리를 가로지르면 교차하는 두 가장자리는 두 가장자리 경로로 대체되며, 두 경로의 중간에 위치한 교차점을 나타내는 새로운 인공 정점이다.[1][2]평면화를 개선하기 위해 교차점이 많은 가장자리를 제거하고 다시 추가하는 평면화 프로세스에 제3의 국부 최적화 단계가 추가되는 경우도 있다.[1]

가장 큰 평면 하위 그래프 찾기

그래프 도면에 증분 평면화를 사용하는 것은 프로세스의 첫 번째 단계에서 가능한 한 큰 평면 그래프를 찾을 때 가장 효과적이다.불행히도 가능한 최대 에지 수(최대 평면 서브그래프 문제[3])를 가진 평면 서브그래프를 찾는 것은 NP-하드, MaxSNP-하드인데, 이는 아마도 문제를 정확하게 해결하는 다항 시간 알고리즘이 존재하지 않거나 임의로 잘 근사하게 되는 다항 시간 알고리즘이 존재하지 않음을 암시한다.[4]

n-vertex 연결 그래프에서 가장 큰 평면 하위 그래프는 최대 3n - 6개의 가장자리를 가지며, 신장 트리는 n - 1개의 가장자리를 가진 평면 하위 그래프를 형성한다.따라서, 스패닝 트리를 찾는 것만으로 근사비의 1/3 이내에서 최대 평면 서브그래프의 근사치를 쉽게 추정할 수 있다.주어진 그래프의 하위 그래프로 큰 부분 2-나무를 찾는 방법에 기초하여 더 나은 근사 비율인 9/4가 알려져 있다.[1][4]또는 평면 하위그래프가 주어진 그래프의 거의 모든 가장자리를 포함시켜 증분 평면화 프로세스에 대해 적은 수의 비 평면적 가장자리만 남겨둘 것으로 예상되는 경우, 실행 시간은 그래프 크기에서는 선형이지만 실행 시간은 아닌 고정 매개변수 추적 가능한 알고리즘을 사용하여 문제를 정확하게 해결할 수 있다.매개변수 [5]k의 다항식또한 이 문제는 정확히 분기와 컷 알고리즘에 의해 해결될 수 있는데, 러닝 타임에 대한 보장은 없지만, 실제로 좋은 성능을 가지고 있다.[1][6]이 매개변수 k는 그래프의 왜도라고 알려져 있다.[3][7]

또한 특정 그래프의 최대 평면 유도 하위 그래프를 찾아 관련 문제에 대한 연구가 있었다.다시 말하지만, 이것은 NP-hard이지만, 몇 개의 정점을 제외한 모든 정점이 유도 서브그래프에 속할 때 고정 매개변수를 추적할 수 있다.[8]Edwards & Farr(2002)는 최대 평면 유도 서브그래프의 크기에 대해 주어진 그래프의 정점 수 n과 그 최대 정도인 Δ의 함수로 3n/(Δ + 1)의 엄격한 경계를 증명했다. 이들의 증거는 이 크기의 유도 서브그래프를 찾기 위한 다항 시간 알고리즘으로 이어진다.[9]

평면화에 모서리 추가

일단 대형 평면 하위 그래프가 발견되면, 나머지 가장자리를 하나씩 고려하여 증분 평면화 과정을 계속한다.그렇게 함으로써, 이미 검토된 가장자리로 형성된 서브그래프의 평면화를 유지한다.그것은 이 서브그래프의 평면 내장물에 각각의 새로운 가장자리를 추가해 교차점이 있는 도면을 형성한 다음 각 교차점을 교차하는 두 가장자리를 세분화한 새로운 인공 꼭지점으로 대체한다.[1][2]이 절차의 일부 버전에서는 에지를 추가하는 순서가 임의적이지만, 동일한 알고리즘을 여러 번 실행하고 찾은 최상의 평면화를 반환하는 순서도 임의 순열로 선택할 수 있다.[1]

이 프로세스의 가장 간단한 형태에서 평면화된 하위 그래프의 평면 내장형은 새로운 가장자리가 추가되는 동안 변경될 수 없다.형성되는 교차 횟수를 최소화하는 방식으로 각각의 새로운 에지를 추가하기 위해서는, 새로운 에지의 끝점을 서로 연결하는 교차할 에지와 내장의 면의 최단 시퀀스를 찾기 위해 현재 임베딩의 이중 그래프에서 최단 경로 알고리즘을 사용할 수 있다.이 프로세스에는 에지당 다항식 시간이 걸린다.[2]

평면화된 서브그래프의 임베딩을 고정하는 것이 결과의 교차점 수 측면에서 반드시 최적의 것은 아니다.실제로 평면 하위 그래프에 하나의 가장자리를 추가하여 형성되는 그래프가 존재하는데, 최적 도면은 두 개의 교차점만 가지고 있지만, 하위 그래프의 평면 포함을 고정하면 선형 교차점이 생성된다.[1]평면 서브그래프에 한쪽 가장자리를 더한 최적의 평면화를 찾는 것과 고정된 임베딩을 유지하는 것 사이의 절충으로서 평면 서브그래프의 모든 임베딩에 대해 검색하여 새로운 가장자리로 형성된 교차 횟수를 최소화하는 것을 찾을 수 있다.[1][10]

참조

  1. ^ a b c d e f g h i Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael; Mutzel, Petra (2014), "Crossings and planarization", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, Florida.
  2. ^ a b c d Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs (1st ed.), Prentice Hall, pp. 215–218, ISBN 0133016153.
  3. ^ a b Chimani, Markus (2008), Computing Crossing Numbers (PDF), Ph.D. dissertation, Technical University of Dortmund, Section 4.3.1, archived from the original (PDF) on 2015-11-16.
  4. ^ a b Călinescu, Gruia; Fernandes, Cristina G.; Finkler, Ulrich; Karloff, Howard (1998), "A better approximation algorithm for finding planar subgraphs", Journal of Algorithms, 27 (2): 269–302, doi:10.1006/jagm.1997.0920, MR 1622397.
  5. ^ Kawarabayashi, Ken-ichi; Reed, Bruce (2007), "Computing crossing number in linear time", Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing (STOC '07), pp. 382–390, doi:10.1145/1250790.1250848, MR 2402463.
  6. ^ Jünger, M.; Mutzel, P. (1996), "Maximum planar subgraphs and nice embeddings: practical layout tools", Algorithmica, 16 (1): 33–59, doi:10.1007/s004539900036, MR 1394493.
  7. ^ Weisstein, Eric W. "Graph Skewness". MathWorld.
  8. ^ Kawarabayashi, Ken-ichi (2009), "Planarity allowing few error vertices in linear time", 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09) (PDF), pp. 639–648, doi:10.1109/FOCS.2009.45, MR 2648441.
  9. ^ Edwards, Keith; Farr, Graham (2002), "An algorithm for finding large induced planar subgraphs", Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Comp. Sci., vol. 2265, Springer, pp. 75–80, doi:10.1007/3-540-45848-4_6, MR 1962420.
  10. ^ Gutwenger, Carsten; Mutzel, Petra; Weiskircher, René (2005), "Inserting an edge into a planar graph", Algorithmica, 41 (4): 289–308, doi:10.1007/s00453-004-1128-8, MR 2122529.