경사수

Slope number
기울기 번호 3이 있는 피터슨 그래프 도면

그래프 그리기와 기하학적 그래프 이론에서, 그래프의 기울기 수는 그래프의 도면에 있는 가장자리의 최소 고유 기울기 수로 정점이 유클리드 평면에서 점으로 표현되고 가장자리는 비사건 정점을 통과하지 않는 선 세그먼트로 표현된다.

전체 그래프

앞서 스콧(1970년)과 제이미슨(1984년) 등 이산 기하학에서 밀접하게 연관된 문제들이 연구되었지만, 그래프의 기울기 수를 결정하는 문제는 웨이드앤추(1994)에 의해 소개되었는데, 이들은 n-베르텍스 완성 그래프 K의n 기울기 수가 정확히 n이라는 것을 보여주었다.이 기울기 번호를 가진 도면은 그래프의 정점을 일반 다각형에 배치하여 형성할 수 있다.

정도와의 관계

최대 도 d의 그래프의 기울기 번호는 분명히two / 이가) 된다. 왜냐하면 도-d 꼭지점에서 입사 가장자리의 대부분이 기울기를 공유할 수 있기 때문이다.더 정확히 말하면, 경사 수는 적어도 그래프의 선형 수목성과 동일하다. 단일 경사면의 가장자리는 선형 숲을 이루어야 하고, 선형 수목성은 차례로 최소⌈ / 이다

수학의 미해결 문제:

최대 4도 그래프에 경계 기울기 수가 있는가?

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

임의로 큰 경사 수를 갖는 최대 도 5의 그래프가 존재한다.[1]그러나 최대 3도의 모든 그래프에는 최대 4개의 기울기 수가 있다.[2] 전체 그래프 K에4 대한 Wade & Chu(1994)의 결과는 이것이 타이트하다는 것을 보여준다.4개의 경사 세트가 모든 도-3 그래프를 그리기에 적합한 것은 아니다. 경사 세트가 평행그램의 측면과 대각선을 구성하는 경우에만 이 목적에 적합하다.특히 3도 그래프는 그 가장자리가 축 평행이거나 정수 격자의 주 대각선과 평행하도록 그릴 수 있다.[3]최대 4도 그래프의 경사가 경계인지 무한경사인지 알 수 없다.[4]

원 패킹과 사분의 트리를 조합하여 경계가 있는 평면 그래프의 경사도 수를 달성하는 Keszegh, Pach & Palvölgy의 방법(2011)

평면 그래프

Keszegh, Pach & Palvölgi(2011년)가 보여주었듯이, 모든 평면 그래프에는 구별되는 기울기의 수가 그래프의 정도의 함수인 평면 직선 도면이 있다.그들의 증거, Malitz 및 공사 다음 Papakostas(1994년)을 경계 각 해상도의 평면 그래프를 정도에 끝나는 것으로 그래프에 최대 평면 그래프 없이 증가하고는 학점이 일정한 요소이고 적용하여 원 정리를 나타내증강 그래프 컬렉션 o.ft각성 사회초기 그래프의 정도가 경계인 경우, 패킹에서 인접한 원의 반지름 사이의 비율도 링 보조기구에 의해 경계를 이루게 되며,[5] 이는 각 그래프의 꼭지점을 원 내의 한 점에 배치하기 위해 쿼드 트리를 사용하면 작은 정수의 비율인 기울기가 생성된다는 것을 의미한다.이 구조에 의해 생성된 구별되는 기울기의 수는 그래프 정도에서 지수적이다.

복잡성

그래프의 기울기 2번 여부를 확인하는 것은 NP 완성이다.[6]이로부터 임의 그래프의 기울기 수를 결정하거나, 근사비 3/2보다 나은 근사비로 근사치를 하는 것이 NP-hard라는 것을 따른다.

평면 그래프의 평면도면이 2번 경사인지, [7]실재자의 실존이론이 평면도면의 최소 경사수를 결정하는 것도 NP완전이다.[8]

메모들

  1. ^ 바라트, 마투셰크 & 우드(2006)와 파치 & 팔불기(2006)에 의해 독자적으로 증명되어 두즈무비치, 수더만 & 우드(2005)가 제기한 문제를 해결했다.Pach & Sharir(2009)의 5.1과 5.2의 정리를 참조한다.
  2. ^ Mukkamala & Szegedy(2009)는 Keszegh 등의 초기 결과를 개선했다. (2008); Pach & Sharir(2009)의 정리 5.3.
  3. ^ Mukkamala & Palvölgy(2012).
  4. ^ Pach & Sharir (2009년).
  5. ^ 한센(1988년).
  6. ^ 포만 외 연구진(1993); 에이드, 홍 & 푸온(2010); 마추치 외 연구진(2011).
  7. ^ Garg & Tamassia(2001년).
  8. ^ 호프만(2016년).

참조

  • Barát, János; Matoušek, Jiří; Wood, David R. (2006), "Bounded-degree graphs have arbitrarily large geometric thickness", Electronic Journal of Combinatorics, 13 (1): R3, MR 2200531.
  • Dujmović, Vida, Suderman, 매튜, 우드, 데이비드 R.(2005년),"정말 그래프 그림 스트레이트", Pach에, 헝가리(교육.)Graph도면:12일 국제 심포지엄, 승무원 2004년, 뉴욕, 뉴욕, 미국, 9월 29-October 2,2004년, 선택된 논문, 강의 노트 컴퓨터 과학으로, 3383 vol., 베를린:Springer-Verlag,를 대신하여 서명함. 122–132, arXiv:cs/0405112, 합치하도록 수정되었다. doi:10.1007/978-3-540-31843-9_14.
  • Eades, 피터,, Seok-Hee, Poon, Sheung-Hung(2010년),"그래프의 직선 그리기에", Eppstein, 데이비드. Gansner, EmdenR.(eds.)Graph도면:17일 국제 심포지엄, 승무원 2009년, 시카고, 일리노이 주, 미국, 9월 22-25인 2009년 수정된 논문, 강의 노트 컴퓨터 과학으로, 5849 vol., 베를린:스프링거,를 대신하여 서명함. 232–243,. doi:10.1007/978-3-642-11805-0_23, MR2680455.
  • Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, MR 1237161.
  • Garg, Ashim; Tamassia, Roberto (2001), "On the computational complexity of upward and rectilinear planarity testing", SIAM Journal on Computing, 31 (2): 601–625, doi:10.1137/S0097539794277123, MR 1861292.
  • Hansen, Lowell J. (1988), "On the Rodin and Sullivan ring lemma", Complex Variables, Theory and Application, 10 (1): 23–30, doi:10.1080/17476938808814284, MR 0946096.
  • Hoffmann, Udo (2016), "The planar slope number", Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016).
  • Jamison, Robert E. (1984), "Planar configurations which determine few slopes", Geometriae Dedicata, 16 (1): 17–34, doi:10.1007/BF00147419, MR 0757792.
  • Keszegh, 벌라주, Pach, 헝가리, Pálvölgyi, Dömötör(2011년),"몇 경사면과 함께 한정적 정도의 평면 그래프 그리는", Brandes, Ulrik에;Cornelsen, 사빈(eds.)Graph도면:18일 국제 심포지엄, GD2010년 콘스탄츠, 독일, 9월 21일부터 24일까지, 2010년에는 선택된 논문, 강의 노트 컴퓨터 과학으로, 6502 vol., 하이델베르크:Springer, 합치하도록 수정되었다.를 대신하여 서명함. 293–304, arXiv:1009.1315, doi:10.1007/978-3-642-18469-7_27, MR2781274.
  • Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör; Tóth, Géza (2008), "Drawing cubic graphs with at most five slopes", Computational Geometry: Theory and Applications, 40 (2): 138–147, doi:10.1016/j.comgeo.2007.05.003, MR 2400539.
  • Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137/S0895480193242931, MR 1271989.
  • Maňuch, 얀, 패터슨, 머레이, Poon, Sheung-Hung, Thachuk, 크리스(2011년),"그래프 논플레이너 회로 직선 그림을 발견 간의 복잡", Brandes, Ulrik에;Cornelsen, 사빈(eds.)Graph도면:18일 국제 심포지엄, GD2010년 콘스탄츠, 독일, 9월 21일부터 24일까지, 2010년에는 선택된 논문, 강의 노트 컴퓨터 과학으로 개정된, 65vol..02하이델베르크:스프링거,를 대신하여 서명함. 305–316, doi:10.1007/978-3-642-18469-7_28, hdl:10281/217381, MR2781275.
  • Mukkamala, Padmini; Szegedy, Mario (2009), "Geometric representation of cubic graphs with four directions", Computational Geometry: Theory and Applications, 42 (9): 842–851, doi:10.1016/j.comgeo.2009.01.005, MR 2543806.
  • Mukkamala, Padmini, Pálvölgyi, Dömötör(2012년),"기본 4경사면과 함께 큐빅 그래프 그리는", 판 크레 벨드, 마크에;Speckmann, 베티나(eds.)Graph도면:19일 국제 심포지엄, GD은 2011년 아인트호벤, 네덜란드, 9월장 21-23절 2011선택 기술을 수정, 강의 노트 컴퓨터 과학으로,. 254–265, 7034, 스프링거,를 대신하여 서명함 vol.. arXiv:1106.1973, doi:10.1007/978-3-642-25878-7_25.
  • Pach, János; Pálvölgyi, Dömötör (2006), "Bounded-degree graphs can have arbitrarily large slope numbers", Electronic Journal of Combinatorics, 13 (1): N1, MR 2200545.
  • Pach, János; Sharir, Micha (2009), "5.5 Angular resolution and slopes", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.
  • Scott, P. R. (1970), "On the sets of directions determined by n points", American Mathematical Monthly, 77: 502–505, doi:10.2307/2317384, MR 0262933.
  • Wade, G. A.; Chu, J.-H. (1994), "Drawability of complete graphs using a minimal slope set", The Computer Journal, 37 (2): 139–142, doi:10.1093/comjnl/37.2.139.