For $(W,S)$ an arbitrary Coxeter system and any $y \in W$, we investigate the condition that the Bruhat graph for the interval $[1,y]$ can be cubulated, meaning roughly that this graph can be spanned by a product of subintervals of $\mathbb{Z}$. Results of Carrell-Peterson and Elias-Williamson imply that if $[1,y]$ can be cubulated, then the Kazhdan-Lusztig polynomial $P_{x,y} = 1$ for all $x \leq y$. We consider the converse to this result. For $(W,S)$ finite and $w_0$ the longest element in $W$, so that $P_{x,w_0} = 1$ for all $x \in W$, we use normal form forests to construct cubulations of $[1,w_0]$ in types $A$ and $B/C$. However, in some exceptional types, we determine elements $y \in W$ such that $P_{1,y} = 1$ but $[1,y]$ cannot be cubulated. We then prove that if there are infinitely many $y \in W$ such that $[1,y]$ can be cubulated, then $(W,S)$ must be of type $\tilde{A}_n$ for some $n \geq 1$. Finally, for $(W,S)$ of type $\tilde{A}_2$, we exhibit a cubulation of $[1,y]$ for each of the infinitely many $y \in W$ such that $P_{x,y} = 1$ for all $x \leq y$.