An AV Clip generated by multiplexing video and graphics streams is recorded on a BD-ROM. The graphics stream is a sequence of PES packets. The PES packets include ODSs (Object Definition Segments) carrying graphics data and PCSs (Presentation Control Segments) carrying control information. A PCS indicates that graphics data in a preceding ODS in the arrangement is to be displayed at a predetermined time in a state of being overlaid on the video stream. The PCS and the preceding ODS belong to different DSs, and the graphics data in the preceding ODS may be non-referenced graphics data that is not referenced by a PCS which belongs to the same DS as the preceding ODS.