Planar Graph Blocking for External Searching

Surender Baswana, Sandeep Sen

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


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.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems