일반화 된 평면 그래프 및 일반화 된 외부 평면 그래프 할 수 있습니다. 그래프 에 대해 알려진

모든 평면 그래프 , 외부 평면 그래프 | E | 3 | V | 6 ,
각각 | E | 2 | V | 3 , 모든 서브 그래프에 대한 G = ( V , E )G .

G=(V,E)

|E|3|V|6


|E|2|V|3

G=(V,E)

G


또한 (외부) 평면 그래프는 다항식 시간으로 인식 할 수 있습니다.

그래프 에 대해 알려진 것은 | E | 3 | V | 6
(RESP. | E |2 | V |3 )에 대한 모든 서브 그래프 G = ( V , E )G ? 다항식 시간으로 인식 할 수 있습니까?

G=(V,E)

|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

26=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은 매우 일반적인 외부 평면 그래프를 재귀 적으로 얻을 수 있음을 증명했습니다.

케이2

3 개의 소위 Henneberg 이동
(1도 정점 추가, 2도 정점 추가, 특정 종류의 3도 정점 추가).

이러한 특성은 일반화 된 외부 평면 그래프에 대한 첫 번째 다항식 인식을 제공합니다.

일반화 된 평면 그래프 와 관련된 일부 설명 은 이 백서 의 마지막 섹션에서 찾을 수 있습니다 . 일반화 된 평면 그래프를 특성화하고 인식하는 것은 여전히 ​​흥미로운 흥미로운 질문으로 남아 있습니다.


답변