접촉 그래프

Contact graph

그래프 이론의 수학 영역에서 접점 그래프 또는 접선 그래프는 정점이 기하학적 객체(예: 곡선, 선 세그먼트 또는 다각형)로 표현되며, 가장자리가 특정 개념에 따라 두 물체가 접촉(교차가 아님)하는 것에 해당하는 그래프다.[1]이것은 교차 그래프의 개념과 유사하지만, 기초적인 물체가 서로 교차하도록 허용되는 방법을 제한하는 것은 그것과 다르다.

원 패킹 정리에는[2] 모든 평면 그래프를 원의 접촉 그래프로 나타낼 수 있다고 명시되어 있다.단위 원의 접촉 그래프를 페니 그래프라고 한다.[3]삼각형,[4] 직사각형,[5] 정사각형,[6][7] 선 세그먼트 또는 원형 호의[8] 접촉 그래프로서의 표현도 연구되었다.

참조

  1. ^ Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten (2013), "Equilateral L-contact graphs", in Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, vol. 8165, Springer, pp. 139–151, arXiv:1303.1279, doi:10.1007/978-3-642-45043-3_13
  2. ^ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88: 141–164
  3. ^ Pisanski, Tomaž; Randić, Milan (2000), "Bridges between geometry and graph theory" (PDF), in Gorini, Catherine A. (ed.), Geometry at Work, MAA Notes, vol. 53, Cambridge University Press, pp. 174–194, MR 1782654; 특히 페이지 176 참조
  4. ^ de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (1994), "On triangle contact graphs", Combinatorics, Probability and Computing, 3 (2): 233–246, doi:10.1017/S0963548300001139, MR 1288442
  5. ^ Buchsbaum, Adam L.; Gansner, Emden R.; Procopiuc, Cecilia M.; Venkatasubramanian, Suresh (2008), "Rectangular layouts and contact graphs", ACM Transactions on Algorithms, 4 (1): Art. 8, 28, arXiv:cs/0611107, doi:10.1145/1328911.1328919, MR 2398588
  6. ^ Klawitter, Jonathan; Nöllenburg, Martin; Ueckerdt, Torsten (2015), "Combinatorial properties of triangle-free rectangle arrangements and the squarability problem", Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9411, Springer, pp. 231–244, arXiv:1509.00835, doi:10.1007/978-3-319-27261-0_20
  7. ^ Hliněný, Petr (2001), "Contact graphs of line segments are NP-complete" (PDF), Discrete Mathematics, 235 (1–3): 95–106, doi:10.1016/S0012-365X(00)00263-6, MR 1829839
  8. ^ Alam, Md. Jawaherul; Eppstein, David; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey; Schulz, André; Ueckerdt, Torsten (2015), "Contact graphs of circular arcs", Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9214, Springer, pp. 1–13, arXiv:1501.00318, doi:10.1007/978-3-319-21840-3_1
Stub icon

이 콤비네이터 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.