Data access time becomes the main bottleneck in applications dealing
with large-scale graphs. Cache-oblivious layouts, constructed to minimize the
geometric mean of arc lengths of graphs, have been adapted to reduce data access
time during random walks on graphs. In this paper, we present a constant factor
approximation algorithm for the Minimum Geometric Mean Layout (MGML)
problem for bounded-degree planar graphs. We also derive an upper bound for
any layout of the MGML problem. To the best of our knowledge, these are the
first results for the MGML problem with bounded-degree planar graphs.