A note on caterpillar-embeddings with no two parallel edges (Q1772131)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on caterpillar-embeddings with no two parallel edges |
scientific article |
Statements
A note on caterpillar-embeddings with no two parallel edges (English)
0 references
15 April 2005
0 references
The authors prove in their paper the following: Let \(C\) be any given caterpillar on \(n\) vertices, and let \(G\) be any set of \(n\) points in general position in the plane. Then there is a rectilinear embedding of \(C\) in the plane so that the vertices of \(C\) are the points of \(G\) and every pair of edges of \(C\) have different directions. In fact, they prove a slightly stronger result. Their result proves a conjecture of Robert E. Jamison. As an open problem the authors ask if the result of their paper remains true if \(C\) is any tree on \(n\) vertices. If the set of points \(G\) is the set of vertices of a regular \(n\)-gon this problem is equivalent to the so-called Harmonic Tree Conjecture.
0 references
caterpillar
0 references
embedding
0 references