Abstract We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and downdepth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded upor down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded upand down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing upand down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. We view our results as a natural step towards understanding the complexity of acyclic planning with bounded treewidth and other parameters.