Not the freezer, too cold, refrigerator. Li-Ions freeze around -40F. A good home freezer can cycle as low as -20F. That's why the chart only goes down to 0 degrees centigrade. Very cold temperatures even above freezing temperature of the electrolyte damage the cells.
That chart is for a Lithium Cobalt chemistry (ICR). It has the shortest shelf life. The Lithium Manganese (IMR) and Lithium Polymer (flat cell) chemistries hold up around 50% better in both cycle life and shelf life.
A Li-Ion is considered worn out when it has 40% of its original charge capacity. For an ICR cell stored with a full charge at room temperature, you can see from the chart that's 3 years. For a cell at 40% charge stored in the refrigerator, it's almost 10 times longer. For a cell with 40% charge stored at room temperature, it's 5 times longer.
Some battery makers recommend against putting cells in cold storage longer than a year since the cold can damage electrolytes over the long term. Manufacturers typically store cells with 40% charge at room temperature in their warehouses.
Like any rechargeable battery, Li-Ion cells have cycle life. For an ICR cell, it's usually 300 full charge-discharge cycles. So, for example, if you routinely run one down half way then charge it, you'll get 600 charges out of before it gets to 40% of its original charge capacity. Personally, I start to really notice a reduction when they get to around 70% of their original capacity so half those numbers would be a more realistic cycle life for me.
Oh, 40% charge is approximately 3.8V measured at the cell with no load. It varies a bit depending on chemistry, but 3.8V will get you close enough. You don't want to store them with too low of a charge since they lose capacity with age. Also, protected cells have a tiny full time draw due to the protection circuitry. For example, storing a cell at 3V for a year could result in the cell dropping below critical voltage. Low voltages damage Li-Ion cells and if discharged deep enough, they will not recharge. Though, voltages as low as 3.5V would probably still be fine for the long term.