동시 임베딩

Simultaneous embedding

동시 임베딩은 두 그래프 내에서 교차되는 것을 피하면서 두 개 이상의 서로 다른 그래프를 라벨이 붙은 정점 집합에 시각화하는 그래프 그리기와 정보 시각화 기법이다.한 그래프의 가장자리와 다른 그래프의 가장자리 사이의 교차점이 허용된다.[1]

가장자리가 폴리선이나 곡선으로 그려질 수 있는 경우 평면의 임의 위치에서 정점을 교차하지 않고 평면 그래프를 그릴 수 있으며, 이때 동일한 정점 배치가 동시 내장 기능을 제공한다.[1]

두 가지 제한된 모델이 있다: 각 그래프를 더 복잡한 곡선보다는 가장자리를 나타내는 선 세그먼트로 평면적으로 그려야 하는 동시 기하학적 내장, 주어진 두 개의 그래프를 평면 그래프의 하위 등급으로 제한하고, 가장자리에서 곡선이나 굴곡이 허용되는 고정된 가장자리로 동시 내장하지만두 그래프의 y 가장자리는 두 도면에서 동일한 곡선으로 표시되어야 한다.[1]제한되지 않은 모델에서 두 개의 평면 그래프는 동시에 내장될 수 있다.

정의

동시 임베딩은 두 그래프 내에서 교차되는 것을 피하면서 두 개 이상의 서로 다른 그래프를 라벨이 붙은 정점 집합에 시각화하는 그래프 그리기와 정보 시각화 기법이다.한 그래프의 가장자리와 다른 그래프의 가장자리 사이의 교차만 허용된다. 이는 허용되지 않는 동일한 그래프의 두 가장자리 사이의 교차일 뿐이다.[1]

가장자리가 폴리선 또는 곡선으로 그려질 수 있는 경우 평면 그래프는 평면의 임의 위치에 정점을 가진 교차 없이 그려질 수 있다.두 그래프에 동일한 꼭지점 배치를 사용하면 두 그래프를 동시에 포함시킬 수 있다.연구는 두 그래프에서 가장자리 사이의 교차점이 거의 없거나 구부러진 부분이 거의 없는 도면을 찾는 데 초점을 맞추고 있다.[1]

두 개의 제한된 모델이 있다: 동시 기하학적 내장 및 고정된 가장자리의 동시 내장. 가장자리에서 곡선 또는 굴곡이 허용되지만, 두 그래프에 존재하는 가장자리는 두 도면에서 모두 동일한 곡선으로 표시되어야 한다.동시 기하학적 임베딩이 존재하면 자동으로 고정된 가장자리가 있는 동시 임베딩이기도 하다.[1]

두 개 이상의 그래프에 동시 내장 문제가 있는 경우 모든 입력 그래프 쌍이 서로 동일한 교차점, 즉 그래프의 가장자리와 꼭지점 집합이 해바라기를 형성한다고 가정하는 것이 표준이다.이 제약조건은 해바라기 교차로로 알려져 있다.[1]

동시 임베딩은 같은 색상의 가장자리 사이에 교차하지 않고 주어진 그래프의 직선 도면에 필요한 최소 에지 색상 수, 주어진 그래프의 모든 가장자리를 덮을 수 있는 평면 서브그래프의 최소 수, 기하학적 두께와 밀접한 관련이 있다.특히 주어진 그래프의 두께는 두 개, 그래프의 가장자리를 동시 임베딩이 있는 두 개의 서브그래프로 분할할 수 있는 경우, 기하학적 두께는 두 개, 가장자리를 동시 임베딩이 있는 두 개의 서브그래프로 분할할 수 있는 경우다.[2]

기하학

동시 기하학적 내장에서는 각 그래프를 더 복잡한 곡선보다는 가장자리를 나타내는 선 세그먼트가 있는 평면 그래프로 그려야 하며, 주어진 두 그래프를 평면 그래프의 하위 등급으로 제한해야 한다.동시 기하학적 내장에 대한 많은 결과는 주어진 두 그래프 정점의 데카르트 좌표를 두 그래프의 속성에서 도출할 수 있다는 생각에 기초한다.이러한 유형의 가장 기본적인 결과 중 하나는 동일한 꼭지점에 있는 두 개의 경로 그래프가 항상 동시 내장되어 있다는 사실이다.그러한 내장을 찾으려면 첫 번째 경로에서 정점 위치를 x좌표로, 두 번째 경로에서 동일한 정점 위치를 y좌표로 사용할 수 있다.이와 같이 첫 번째 길은 자동으로 비자기 교차되는 곡선의 일종인 x-모노톤 폴리선으로 그려지고, 두 번째 경로는 y-모노톤 폴리선으로 비슷하게 그려진다.[3]

이 유형의 도면은 정점을 그래프 크기의 선형 치수의 정수 격자에 배치한다.유사하게 정의된 레이아웃도 작동하며, 두 그래프가 모두 애벌레이거나 둘 다 사이클 그래프일 때 더 크지만 여전히 선형 그리드 크기가 있다.선형 치수의 그리드에 동시에 내장하는 것도 모든 별인 그래프 수에 상관없이 가능하다.항상 동시 임베딩을 허용하지만 더 큰 그리드 크기가 필요할 수 있는 다른 그래프 유형의 쌍에는 휠 그래프와 사이클 그래프, 트리와 일치를 포함하거나 두 그래프 모두 최대 2도를 갖는 그래프 쌍이 포함된다.그러나 동시에 기하학적 내장을 포함하지 않는 평면 그래프와 일치 또는 트리 및 경로 쌍이 존재한다.[4][5][6]

두 그래프가 동시 기하학적 내장을 허용하는지 여부를 테스트하는 것은 NP-hard이다.[1][7]더 정확히 말하면 실존의 실존이론에 대해서는 완결된 것이다.이 결과의 증거는 동시에 기하학적 임베딩이 있는 일부 그래프 쌍의 경우, 그릴 수 있는 가장 작은 그리드는 두 배의 지수적 크기를 가지고 있다는 것을 암시한다.[8][2] 동시 기하학적 임베딩이 존재하면 자동으로 고정된 가장자리가 있는 동시 임베딩이기도 하다.[1]

고정 모서리

고정된 가장자리가 있는 동시 임베딩에서는 가장자리에 곡선 또는 곡선이 허용되지만 두 그래프에 있는 가장자리는 두 도면에서 동일한 곡선으로 표시되어야 한다.[1]다른 유형의 입력은 항상 내장되어 있거나 때로는 불가능할 수 있는 것으로 분류하는 것은 그릴 두 가지 유형의 그래프뿐만 아니라 교차점의 구조에도 달려 있다.예를 들어, 주어진 두 개의 그래프가 모두 외부 평면 그래프이고 그 교차점이 선형 숲일 때, 모든 것이 다항식 영역의 그리드에 속하는 정점 좌표와 굴곡점일 때 그러한 내장을 항상 찾을 수 있다.그러나 그러한 내장이 없는 더 복잡한 교차점을 가진 다른 쌍의 외부 평면 그래프가 존재한다.평면 그래프와 트리 쌍에 대해 고정된 가장자리가 있는 동시 임베딩도 가능하다.[9][10][11]

수학의 미해결 문제:

주어진 두 그래프에 대해 고정된 가장자리가 있는 동시 임베딩을 다항식 시간에 찾을 수 있는가?

(수학에서 더 풀리지 않은 문제)

주어진 두 개의 그래프에 대해 고정된 가장자리가 있는 동시 임베딩의 존재를 다항 시간 내에 테스트할 수 있을지는 아직 미지수다.그러나 세 개 이상의 그래프의 경우 NP-완전성이 문제다.고정된 가장자리가 있는 동시 임베딩이 존재하는 경우, 외부 평면 그래프 쌍과 Biconected 그래프 쌍, 즉 교차점이 서로 연결된 그래프 쌍의 경우 다항식 시간에 찾을 수 있다.[1][12][13][14]

무제한

두 개의 평면 그래프는 동시에 내장될 수 있다.이 작업은 다항식 영역의 그리드에서 수행될 수 있으며, 가장자리당 최대 두 개의 굴곡부가 있을 수 있다.어떤 2개의 서브 해밀턴 그래프도 최대 에지당 하나의 벤딩으로 동시에 내장된다.[1][10][15]

참조

  1. ^ a b c d e f g h i j k l Bläsius, Thomas; Kobourov, Stephen G.; Rutter, Ignaz (2013), "Simultaneous embedding of planar graphs", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 349–383, ISBN 9781420010268
  2. ^ a b Duncan, Christian; Eppstein, David; Kobourov, Stephen G. (2004), "The geometric thickness of low degree graphs", Proc. 20th ACM Symposium on Computational Geometry, ACM, pp. 340–346, arXiv:cs.CG/0312056, doi:10.1145/997817.997868, S2CID 7595249.
  3. ^ 블라이시우스, 코부로프 & 러터(2013), 정리 11.1.
  4. ^ Blaiusius, Kobourov & Rutter(2013), 그림 11.2.
  5. ^ Brass, Peter; Cenek, Eowyn; Duncan, Christian 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 Theory & Applications, 36 (2): 117–130, doi:10.1016/j.comgeo.2006.05.006, MR 2278011.
  6. ^ Cabello, Sergio; van Kreveld, Marc; Liotta, Giuseppe; Meijer, Henk; Speckmann, Bettina; Verbeek, Kevin (2011), "Geometric simultaneous embeddings of a graph and a matching", Journal of Graph Algorithms and Applications, 15 (1): 79–96, CiteSeerX 10.1.1.487.4749, doi:10.7155/jgaa.00218, MR 2776002.
  7. ^ Estrella-Balderrama, 알레한드로, 개스너, 엘리자베트, 윙거, 마이클 Percan, Merijam, Schaefer마커스, 슐츠, 마이클(2008년),"동시에 기하학적 그래프 embeddings"Graph도면:15일 국제 심포지엄, GD2007년, 시드니, 호주, 9월 24–26, 2007, 수정된 논문, 강의 노트 컴퓨터 과학으로, 베를린:스프링거,를 대신하여 서명함 4875 vol..280–290, doi:10.1007/978-3-540-77537-9_28, MR2427826.
  8. ^ Cardinal, Jean; Kusters, Vincent (2015), "The complexity of simultaneous geometric graph embedding", Journal of Graph Algorithms and Applications, 19 (1): 259–272, doi:10.7155/jgaa.00356, MR 3344782, S2CID 12662906.
  9. ^ Blaiusius, Kobourov & Rutter(2013), 그림 11.5.
  10. ^ a b Di Giacomo, Emilio; Liotta, Giuseppe (2007), "Simultaneous embedding of outerplanar graphs, paths, and cycles", International Journal of Computational Geometry & Applications, 17 (2): 139–160, doi:10.1142/S0218195907002276, MR 2309902.
  11. ^ Frati, Fabrizio (2007), "Embedding graphs simultaneously with fixed edges", Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18–20, 2006, Revised Papers, Lecture Notes in Computer Science, vol. 4372, Berlin: Springer, pp. 108–113, doi:10.1007/978-3-540-70904-6_12, MR 2393910.
  12. ^ Fowler, J. Joseph; Jünger, Michael; Kobourov, Stephen G.; Schulz, Michael (2011), "Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges", Computational Geometry Theory & Applications, 44 (8): 385–398, doi:10.1016/j.comgeo.2011.02.002, MR 2805957.
  13. ^ 개스너, 엘리자베트, 윙거, 마이클 Percan, Merijam, Schaefer마커스, 슐츠, 마이클(2006년),"고정 가장자리의 동시 그래프 embeddings", Graph-Theoretic 개념 컴퓨터 과학으로:32위 국제 워크숍 WG 2006년, 베르겐, 노르웨이, 6월 22-24, 2006년 수정된 페이퍼(PDF), 강의 노트 컴퓨터 과학으로, 4271 vol., 베를린:Springer,. Pp. 325–335, doi:10.1007/11917496_29, MR2290741.
  14. ^ Haeupler, Bernhard; Jampani, Krishnam Raju; Lubiw, Anna (2013), "Testing simultaneous planarity when the common graph is 2-connected", Journal of Graph Algorithms and Applications, 17 (3): 147–171, arXiv:1009.4517, doi:10.7155/jgaa.00289, MR 3043207.
  15. ^ Di Giacomo, Emilio; Liotta, Giuseppe (2005), "A note on simultaneous embedding of planar graphs", 21st European Workshop on Computational Geometry (PDF), Eindhoven University of Technology.