  A $k$-leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves
of $T$ and whose edges connect pairs of leaves whose distance in $T$ is at most
$k$. A graph is a leaf power if it is a $k$-leaf power for some $k$. Over 20
years ago, Nishimura et al. [J. Algorithms, 2002] asked if recognition of leaf
powers was in P. Recently, Lafond [SODA 2022] showed an XP algorithm when
parameterized by $k$, while leaving the main question open. In this paper, we
explore this question from the perspective of two alternative models of leaf
powers, showing that both a linear and a star variant of leaf powers can be
recognized in polynomial-time.
