We estimate and characterize the edge congestion-sum measure for embeddings of various graphs such as cycles, wheels, and generalized wheels into arbitrary trees. All embedding algorithms apply an interesting general technique based on the consecutive label property. Our algorithms produce optimal values of sum of dilations and sum of edge-congestions in linear time. © 2004 Wiley Periodicals, Inc.