Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

Bounds on the Metric Dimensions for Families of Planar Graphs

Booth Id:



Finalist Names:
Quines, Carl Joshua (School: Blackebergs Gymnasium)
Sun, Michael

The concept of metric dimension has applications in a variety of fields, such as chemistry, robotic navigation, and combinatorial optimization. Three bounds on the metric dimensions for different families of planar graphs based on the number of vertices are discussed. The first two results concern outerplanar graphs: Hamiltonian outerplanar graphs have a metric dimension of at most half the number of vertices, and outerplanar graphs in general have a metric dimension of at most two-thirds the number of vertices. The final result deals with maximal planar graphs, which have a metric dimension of at most three-fourth the number of vertices. It is conjectured that the metric dimension of maximal planar graphs in general is at most two-fifth the number of vertices. Applications of the results in various fields are discussed.

Awards Won:
Second Award of $2,000