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


A Note on Caterpillar-Embeddings with No Two Parallel Edges
Authors:Daniel J Kleitman  Rom Pinchasi
Institution:(1) Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139-4307, USA
Abstract:Let G be a set of n points in general position (i.e., no three points are on a line) in the plane, and let C be a caterpillar on n vertices. We show that one can always find a rectilinear embedding of C in the plane such that the vertices of C are the points of G and no two edges of C go to parallel segments. This proves a conjecture of Robert E. Jamison.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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