Planar graph blocking for external searching

Baswana, Surender ; Sen, Sandeep (2002) Planar graph blocking for external searching Algorithmica, 34 (3). pp. 298-308. ISSN 0178-4617

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to Springer.
Keywords:External; Graph; Mesh; Planar; Searching
ID Code:53435
Deposited On:08 Aug 2011 12:09
Last Modified:08 Aug 2011 12:09

Repository Staff Only: item control page