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 等数据库收录! |
|