각도 분해능(그래프 도면)

그래프 도면에서 그래프의 각 분해능은 도면의 공통 정점에서 만나는 두 가장자리에 의해 형성된 가장 날카로운 각이다.

특성.

정점도에 대한 관계

Formann 외 연구진(1993)은 최대 도 d의 그래프의 모든 직선 도면에 각도 분해능이 최대 2㎛/d인 것을 관찰했다. v가 도 d의 정점인 경우 v가 입사하는 가장자리가 v 주위의 공간을 총 각도 2㎛의 d웨지로 분할하고 이들 웨지 중 가장 작은 부분은 최대 2㎛/d의 각도를 가져야 한다.더욱 강력한 것은, 그래프가 d-규칙적인 경우, 도면의 볼록한 선체에 있는 꼭지점에 대해 달성할 수 있는 최상의 분해능이기 때문에, 각 분해능이 ${\displaystyle \frac{d}{}}$d - ${\displaystyle \frac{1}{}}${\$displaystyle${\$frac {\pi}{d-1}$ 미만이어야 한다$.$

그래프 컬러링과의 관계

Formann 외 연구진(1993)에서 알 수 있듯이, 그래프 G의 가능한 가장 큰 각도 분해능은 정점 쌍이 G의 거리가 최대 2가 될 때마다 가장자리에 의해 연결되는 정점 집합의 그래프인 정점 G의² 색수와 밀접하게 관련되어 있다.G를² χ 색상으로 채색할 수 있는 경우, 정규 >곤의 꼭지점에 구별되는 색상을 할당하고 G의 각 꼭지점을 같은 색상으로 다각형 꼭지점에 가깝게 배치하여 χ/ - - ε로 G를 그릴 수 있다.이 구조를 사용하여, 그들은 최대 도 d를 가진 모든 그래프는 각 분해능이 1/d에² 비례하는 도면을 가지고 있다는 것을 보여주었다.이 바인딩은 거의 타이트한 편이며, 그들은 확률론적 방법을 사용하여 도면이 모두 각도 분해능 $O{\displaystyle (\frac{\mathrm{로그}d}{}}$ ${\displaystyle \frac{{d\mathrm{}}^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$) ${\$ d$}{d^{2}}:}\오른쪽)}$인 그래프의 존재를 증명했다$.$

최적도면의 존재

Formann 외 연구진(1993)은 가능한 최대 각도 분해능을 달성하는 도면이 없는 그래프가 존재한다는 것을 보여주는 예를 제공했다. 대신, 이 그래프들은 각도 분해능이 도달하지 않고 어떤 제한값으로 향하는 도면군을 가지고 있다.구체적으로, 그들은 > > 0에 대한 각도 분해능 //3 - ε 도면이 있는 11-Vertex 그래프를 전시했지만, //3 도면은 정확히 가지고 있지 않다.

그래프의 특수 클래스

나무들

모든 트리는 완벽한 각도 분해능으로 알려진 속성인 각 꼭지점 주위에 가장자리가 균등하게 간격을 두고 그려질 수 있다.또한, 각 꼭지점을 중심으로 가장자리가 자유롭게 퍼머될 수 있는 경우, 교차하지 않고 모든 가장자리 단위 길이 이상을 가지며, 전체 도면 피팅이 다항식 영역의 경계 상자 내에서 가능하다.그러나 각 정점 주위의 가장자리의 주기적 순서가 이미 문제에 대한 입력의 일부로 결정되었다면, 교차 없이 완벽한 각도 분해능을 달성하는 것은 때때로 지수 영역을 필요로 할 수 있다.^[1]

외부 평면 그래프

도면의 볼록한 선체에 있는 정점이 도면의 입사 모서리를 동일한 간격으로 둘 수 없기 때문에 외부 평면 그래프의 경우 완벽한 각도 분해능이 항상 가능한 것은 아니다.그럼에도 불구하고, 최대도 d의 모든 외부 평면 그래프는 1/d에 비례하는 각도 분해능의 외부 평면도를 가지고 있다.^[2]

평면 그래프

최대 도 d를 갖는 평면 그래프의 경우, 평면 그래프의 제곱은 d에 비례하는 색수를 가져야 하기 때문에 Formann 등(1993)의 사각형 색상 기법은 각도 분해능이 1/d에 비례하는 도면을 제공한다.좀 더 정밀하게, 웽거 감독은 1977년에 있는 평면 그래프의 제곱의 색 수 대부분의 정도 들 것(d+5,3d2+1){\displaystyle \max \left(d+5,{\frac{3D}{2}}+1\right)}에서, 그리고 색 수에 대부분의 5d3+O(1){\displaystyle{\frac{5d}{3}}+O(1)}.[3] 하지만, 이 알려져 있다 추측했다. 나이 기법에서 기인하는 눈금은 일반적으로 평면적이 아니다.

일부 평면 그래프의 경우 평면 직선 도면의 최적 각도 분해능은 O(1/d³)이며, 여기서 d는 그래프 수준이다.^[4]또한 이러한 도면은 도면에서 가장 짧은 가장자리보다 지수 인자에 의해 매우 긴 가장자리를 사용하도록 강제될 수 있다.말리츠 & 파파코스타스(1994)는 원 패킹 정리 및 링 보조마사를 사용하여 최대 도 d를 갖는 모든 평면 그래프는 각 분해능이 최악인 평면도를 가지고 있으며, 그래프의 정점 수와 무관하게 d의 지수함수가 있음을 보여주었다.

계산 복잡성

d = 4인 특별한 경우라도 최대 d의 주어진 그래프가 각도 분해능 2㎛/d의 도면을 가지고 있는지 여부를 결정하는 것은 NP-힘이다.^[5]단, 잎을 무한대로 확장하여 평면을 볼록하게 분할하는 나무 도면과 각 경계면이 중심 대칭 폴리곤인 평면 그래프의 도면 등 특정 제한된 도면 등급의 경우 다항 시간에서 최적의 각도 분해능의 도면을 찾을 수 있다.^[6]

역사

각 분해능은 처음에 Formann 외 연구진(1993)에 의해 정의되었다.

원래 그래프의 직선 도면에 대해서만 정의되었지만, 이후 저자들은 가장자리가 다각형 체인,^[7] 원형 호 또는 ^[8]스플라인 곡선인 도면의 각도 분해능도 조사하였다.^[9]

그래프의 각도 분해능은 그래프의 도면에서 교차점에 의해 형성된 각도인 교차 분해능과 밀접한 관련이 있다.특히, RAC 도면은 이러한 각도가 가능한 가장 큰 교차각인 모든 직각임을 확인하고자 한다.^[10]

메모들

참조