For varietal trials, either using a one-way design or a block design, we consider situations in which a temporal or spatial trend is present over experimental units. It is assumed that the trend can be approximated by a polynomial of degree p (p is an integer), taking its values on the time orders or plot positions on which observations will be taken. Analysis of covariance models are employed with the trend terms as the covariates. Algorithms are developed in this context for searching for both efficient one-way designs and efficient block designs;If p = 1, a block design that allows statistical inference about treatment contrasts to be the same for the assumed covariance model and the assumed model but without the presence of the covariates, is called a linear trend-free block design. We present and explore a connection between graph theory and linear trend-free block designs. This connection extends the theoretically known classes of block designs that can be converted, without changing their treatment-block incidence matrices, to a linear trend-free block design.