Abstract:
We present an improved scheme for storing a planar graph in
external-memory so that any online path can be traversed in an
I-O efficient way. 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.