  We introduce the notion of an $r$-visit of a Directed Acyclic Graph DAG
$G=(V,E)$, a sequence of the vertices of the DAG complying with a given rule
$r$. A rule $r$ specifies for each vertex $v\in V$ a family of $r$-enabling
sets of (immediate) predecessors: before visiting $v$, at least one of its
enabling sets must have been visited. Special cases are the $r^{(top)}$-rule
(or, topological rule), for which the only enabling set is the set of all
predecessors and the $r^{(sin)}$-rule (or, singleton rule), for which the
enabling sets are the singletons containing exactly one predecessor. The
$r$-boundary complexity of a DAG $G$, $b_{r}\left(G\right)$, is the minimum
integer $b$ such that there is an $r$-visit where, at each stage, for at most
$b$ of the vertices yet to be visited an enabling set has already been visited.
By a reformulation of known results, it is shown that the boundary complexity
of a DAG $G$ is a lower bound to the pebbling number of the reverse DAG, $G^R$.
Several known pebbling lower bounds can be cast in terms of the
$r^{(sin)}$-boundary complexity.
  A visit partition technique for I/O lower bounds, which generalizes the
$S$-partition I/O technique introduced by Hong and Kung in their classic paper
"I/O complexity: The Red-Blue pebble game". The visit partition approach yields
tight I/O bounds for some DAGs for which the $S$-partition technique can only
yield an $\Omega(1)$ lower bound.
