A note on caterpillar-embeddings with no two parallel edges (Q1772131)

From MaRDI portal





scientific article; zbMATH DE number 2156868
Language Label Description Also known as
default for all languages
No label defined
    English
    A note on caterpillar-embeddings with no two parallel edges
    scientific article; zbMATH DE number 2156868

      Statements

      A note on caterpillar-embeddings with no two parallel edges (English)
      0 references
      0 references
      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
      0 references
      caterpillar
      0 references
      embedding
      0 references

      Identifiers