首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Geometric graphs with no two parallel edges
Authors:Rom Pinchasi
Institution:(1) Israel Institute of Technology Technion, Technion City, Haifa, 32000, Israel
Abstract:We give a simple proof for a theorem of Katchalski, Last, and Valtr, asserting that the maximum number of edges in a geometric graph G on n vertices with no pair of parallel edges is at most 2n−2. We also give a strengthening of this result in the case where G does not contain a cycle of length 4. In the latter case we show that G has at most 3/2(n−1) edges.
Keywords:05C10
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号