On the number of edges in 3-Fan-Crossing free graphs containing a plane spanning tree

Abstract

평면 위에 그려진 그래프에서 끝점을 공유하는 변 e1,e2,...,ek이 이들과 끝점을 공유하지 않는 변 e 와 모두 교차하는 것을 k-팬 교차라고 정의한다. k-팬 자유 그래프는 k-팬 교차가 없는 그래프를 의미한다. 2-평면 그래프는 3-팬 자유 그래프이며, 2-평면 그래프에 대한 연구는 아직 널리 이루어지지 않았다. 2-평면 그래프는 최대 5n-10개의 엣지를 가질 수 있으며, 3-팬 자유 그래프에서도 같은 상한이 적용될 것으로 추 측된다. 이 논문에서는 3-팬 교차가 없고 플레인 신장트리를 가지는 그래프에서의 엣지의 수는 최대 5n-10 임을 증명한다.