On the number of edges of a fan-crossing free graph팬 교차가 없는 그래프에서의 엣지의 수의 범위
A graph drawn in the plane with n vertices is fan-crossing free if there is no triple of edges e; f and g, such that e and f have a common endpoint and g crosses both e and f. We prove a tight bound of 4n < 9 on the maximum number of edges of such a graph for a straight-edge drawing. The bound is 4n < 8 if the edges are Jordan curves. We discuss generalizations to radial (k,1)-grid free graphs and monotone graph properties.
- Advisors
- Cheong, Otfriedresearcher; 정지원
- Description
- 한국과학기술원 : 전산학과,
- Publisher
- 한국과학기술원
- Issue Date
- 2013
- Identifier
- 515122/325007 / 020113179
- Language
- eng
- Description
학위논문(석사) - 한국과학기술원 : 전산학과, 2013.2, [ iii, 21 p. ]
- Keywords
Graph Drawing; 그래프 이론; 조합론; Combinatorics
- Appears in Collection
- CS-Theses_Master(석사논문)
- Files in This Item
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.