We examine a characterization of fixed modes in a frequency-domain framework based on the graphical representation of systems with multiple poles. We present a graph-theoretic characterization of the characteristic polynomials of closed-loop systems under arbitrary structural constraints. Based on this characterization, fixed modes are characterized using the weight products of 1-factors of the weighted directed graphs associated with closed-loop systems. It is also shown that the well-known characterization of fixed modes in terms of transmission zeros can be derived from the proposed graph-theoretic characterization.