That's a very interesting need. If you represent your data sparsely, such that you store transitions and timestamps only, then you're unlikely to find a plotting tool that handles this data format. It might worth looking for a .NET control that exists already for this and interfacing with that. But I would prefer a pure LabVIEW solution if possible.
My immediate thought is that you're going to need to create your own graphing tools. If you want to look at the entire signal then you'll need to reinterpret the sparse data in order to use it on a traditional LabVIEW graph, but then you have memory limitations (as you already experienced). The next option, and it might be possible since you're talking about simple rectangular digital signals, would be to draw your own lines with the picture tools and build up your own graph image. You can then re-interpret the sparse data as instructions for plotting a line. It's a little work, but not a great deal.
My ambition then would be to wrap this up as an XControl, including horizontal and vertical scrollbars, so that one can pan through the image (it might need to be redrawn on the fly as the user moves a scrollbar), and zoom in and out (changing the range of values to include in the plotting functions). You won't want to recreate all the functionality of the LabVIEW native graphing tools, but the basics mentioned above wouldn't be too difficult.