We used scanning tunneling microscopy (STM) to investigate high-coverage structures of atomic oxygen on Pt(111). We observe the sequential development of p(2x2) and p(2x1) structures as the oxygen atom coverage increases to about 0.50 ML (monolayer), with the p(2x1) domains growing in three orientations each rotated by 120 degrees relative to one another. Near about 0.40 ML, atomic scale protrusions and chains, approximately 0.17 nm in height, appear between the close-packed rows of the p(2x1) structure. We attribute these features to a Pt oxide chain compound that forms as oxygen atoms adsorb between the oxygen rows of the p(2x1) structure. Prior studies demonstrate that the Pt oxide chains serve as a precursor to bulk oxide formation on Pt(111). As the oxygen coverage increases to 0.75 ML, the chains arrange into an interconnected network of Y-shaped structures with regions locally resembling a honeycomb. Each branch of the Y-structure consists of two to three side-by-side Pt oxide chains about 1.9 to 2.4 nm in length. We suggest that uniaxial strain causes the chains to select specific lengths that are commensurate along the close-packed directions of the Pt(111) substrate, and that stress relief governs the chain branching and formation of an interconnected superstructure. Overall, the STM results demonstrate that Pt oxide chain formation occurs during the early stages of Pt(111) oxidation, and that long-range effects determine the structural characteristics of the resulting chain network. These findings may have implications for understanding applications of Pt oxidation catalysis under lean conditions.