The present invention relates to a recording medium having data structure including graphic data to be used for a menu page etc. of main video data recorded thereon as well as methods and apparatuses for reproducing and recording the data structure. A recording medium of the present invention comprises: a main data stream including at least video data; and a graphic data stream being used for graphic presentation for the recorded main data stream, wherein the graphic data stream includes at least one display set; the display set includes at least one composition segment and at least two definition segments; and a decoding time stamp written in a definition segment within the display set is equal to or greater than a presentation time stamp written in a preceding definition segment.