NP-hard problems on trees Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include minimum vertex cover, maximum independent set, subgraph isomorphism. Name some natural optimization problems that remain NP-hard on trees.
It is NP-complete to determine whether a tree can be embedded into the two-dimensional integer grid, with the tree vertices placed on distinct grid points and the tree edges placed on grid edges.

See e.g. Gregori, IPL 1989.