The adsorption of oxygen on the Ru(0001) surface precovered with submonolayer concentrations of cesium was investigated by means of low energy electron diffraction (LEED), thermal desorption spectroscopy (TDS) and Auger electron spectroscopy (AES). The strong interaction between Cs and O manifests itself in the appearance of a diversity of ordered structures as indicated in a complex Theta(Cs)-Theta(O), phase diagram. The main emphasis has been put on structural aspects of these Cs-O overlayers. Real-space models for several of them are suggested on the basis of fully dynamical LEED calculations, quasi-kinematic LEED simulations and by applying the concept of LEED fingerprinting. The models are discussed in terms of their resemblance to Cs oxide bulk structures. Striking similarities to the CsO2 crystal structure have indeed been found for the oxygen-rich Cs-O phases on the Ru surface, namely the (3 x 2 root 3)rect and the (root 7 x root 7)R19.1 degrees structures, which are observed al a stoichiometry of two oxygen atoms per Cs atom. The common structural element consists of Cs-O-O chains being either twisted or linear. The (root 7 x root 7)R19.1 degrees-Cs-O phase can be observed over a wide Cs coverage range with optimum order always accomplished at an atomic ratio Cs:O=1:2.