모든 평면 그래프 , 외부 평면 그래프 는 | E ‘ | ≤ 3 | V ‘ | – 6 ,
각각 | E ‘ | ≤ 2 | V ‘ | – 3 , 모든 서브 그래프에 대한 G ‘ = ( V ‘ , E ‘ ) 의 G .
|E′|≤3|V′|−6
G′=(V′,E′)
G
또한 (외부) 평면 그래프는 다항식 시간으로 인식 할 수 있습니다.
그래프 에 대해 알려진 것은 | E ‘ | ≤ 3 | V ‘ | – 6
(RESP. | E ‘ | ≤ 2 | V ‘ | – 3 )에 대한 모든 서브 그래프 G ‘ = ( V ‘ , E ‘ ) 의 G ? 다항식 시간으로 인식 할 수 있습니까?
|E′|≤3|V′|−6
|E′|≤2|V′|−3
G′=(V′,E′)
G
편집 (Eppstein의 좋은 답변 후) : 모든 평면 그래프 만족 | E ‘ | ≤ 3 | V ‘ | – 6 모든 서브 그래프에 대한 G ‘ = ( V ‘ , E ‘ ) 의 G 적어도 세 꼭지점 | V ‘ | ≥ 3
G=(V,E)|E′|≤3|V′|−6
G′=(V′,E′)
G
|V′|≥3
. 따라서, “일반화 된 평면 그래프”는이 특성을 만족시키는 것일 것이고, 다항식 시간에서 그것들을 인식하는 것은 (흥미로운) 열린 질문 인 것 같습니다.
답변
Lee와 Streinu (아래 인용)의 표기법에서 두 번째 클래스는 (2,3)-분수 그래프입니다. 다항식 시간으로 그래프가 (k, l)-스파 스인지 테스트하는 알고리즘을 제공합니다. 그러나 평면 그래프 및 은 모든 정점 세트에 대해 부등식이 참이 아니기 때문에 조금 더 복잡합니다. (정확한 경우에는 3 ⋅ 2 − 6 = 0 이므로 두 정점이 모서리로 연결될 수 없습니다.
|이자형‘|≤삼|V‘|−6삼⋅2−6=0
). 따라서 (3,6)-분할 그래프의 클래스 (그 표기법으로 표시)는 빈 그래프로만 구성됩니다. 아마도 그들의 알고리즘은 두 정점 이상의 모든 집합에 대해 불평등이있는 그래프로 확장 될 수 있습니다.
이 오드리; Streinu, Ileana (2008), “피블 게임 알고리즘 및 희소 그래프”, 이산 수학 308 (8) : 1425–1437, doi : 10.1016 / j.disc.2007.07.104 , arxiv : math / 0702129 .
답변
“일반화 된 외부 평면 그래프”또는 (2,3)-분할 그래프에 대해 알려진 것은 무엇입니까? DavidEppstein의 답변에 대한 몇 가지 추가 사실 :
1982 년 이 논문
(롤 1 및 2)에서 Lovász와 Yemini는 일반화 된 외부 평면 그래프 (그들의 표기법에서 일반 독립 그래프 )를 그 그래프로 특성화했습니다.
의 가장자리를 두 배로하는 특성을 갖는 것
지두 포리스트의 경계 분리 결합 인 그래프를 생성합니다.
1970 년에 Henneberg와 Laman은 매우 일반적인 외부 평면 그래프를 재귀 적으로 얻을 수 있음을 증명했습니다.
케이23 개의 소위 Henneberg 이동
(1도 정점 추가, 2도 정점 추가, 특정 종류의 3도 정점 추가).
이러한 특성은 일반화 된 외부 평면 그래프에 대한 첫 번째 다항식 인식을 제공합니다.
일반화 된 평면 그래프 와 관련된 일부 설명 은 이 백서 의 마지막 섹션에서 찾을 수 있습니다 . 일반화 된 평면 그래프를 특성화하고 인식하는 것은 여전히 흥미로운 흥미로운 질문으로 남아 있습니다.