A directed acyclic graph (DAG) is a useful representation of causal structures and partial orderings between variables. In this dissertation, several new testing procedures for multiple hypotheses along a DAG that take into account both the graph structure and side information are presented and studied. These procedures are shown to theoretically and empirically control FDR while increasing power over existing methods under certain scenarios. A generalized DAG testing procedure is also considered that allows one to use more general logical constraints, which can potentially differ for each hypothesis. Extensive simulation studies show promise of attaining theoretical FDR-control. The focus is then shifted to the problem of detecting the directed edges between discrete variables, for which a novel Bayesian model is presented. This model incorporates graph edge sparsity through a sparsity inducing prior, while modeling each node as coming from a conditional distribution in which the variance is a quadratic function of its mean. Extensive simulation studies show the promising nature of this Bayesian model in terms of providing a lower error rate for detecting the directed edges, while having similar power as existing methods.