We present a new approach towards the construction of a genuinely multidimensional high-resolution scheme for computing steady-state solutions of the Euler equations of gas dynamics. The unique advantage of this approach is that the Gauss-Seidel relaxation is stable when applied directly to the high-resolution discrete equations, thus allowing us to construct a very efficient and simple multigrid steady-state solver. This is the only high-resolution scheme known to us that has this property. The two-dimensional scheme is presented in detail. It is formulated on triangular (structured and unstructured) meshes and can be interpreted as a genuinely two-dimensional extension of the Roe scheme. The quality of the solutions obtained using this scheme and the performance of the multigrid algorithm are illustrated by the numerical experiments. Construction of the three dimensional scheme is outlined briefly as well. Sidilkover, David Unspecified Center NAS1-19480...