| Article ID: | iaor20121127 |
| Volume: | 34 |
| Issue: | 3 |
| Start Page Number: | 298 |
| End Page Number: | 308 |
| Publication Date: | Nov 2002 |
| Journal: | Algorithmica |
| Authors: | Baswana Surender, Sen Sandeep |
| Keywords: | combinatorial optimization |
We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I‐O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I‐O efficiency of any storage scheme for well‐shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance.