비평면 그래프의 평면화를위한 알고리즘

Question

비평면 그래프의 평탄화에 널리 사용되는 알고리즘이 있습니까?

현재 부스트 (부스트 그래프 라이브러리)에서 무향 그래프에 대한 직교 평면 레이아웃 알고리즘을 구현할 계획입니다. BGL은 방향이 지정되지 않은 그래프 (Boyer-Myrvold Planarity Testing)의 평면성을 검사하기위한 구현이 있으며이 방법으로 반환 된 평면 삽입을 사용하여 직각 배치를 계획합니다.

그러나 입력 그래프가 평면이 아닌 경우 무엇을해야하는지 잘 모르겠습니다. 그래프를 평면으로 만들기 위해 그런 시나리오에서 반환 된 Kuratowski 하위 그래프로 뭔가를해야합니까?

"비평면 그래프의 평면화"에 대한 Google 검색은 여러 연구 논문을 반환합니다. 어디서부터 시작해야할지 모르겠습니다.

Answer 1

$ K_n $의 지수가 많은 $ K_5 $ 및 $ K_ {3,3} $ 하위 그래프가 있으므로 미성년자는 신경 쓰지 않으므로 직접 치료하는 것은 대단히 효율적이지 않습니다. 나는 다른 사람들이이 문제에 접근하는 방법에 대해 조금 배우기 위해 연구 논문을 뒤집을 것을 제안한다. (a) 합리적인 솔루션을 제공하고 (b) 관심있는 그래프처럼 들리는 속성에주의를 기울여야합니다.