On distances in benzenoid systems

We show that the molecular graph G of a benzenoid hydrocarbon admits an isometric embedding into the Cartesian product of three trees T-1, T-2, and T-3 defined by three directions of the host hexagonal grid. Namely, to every vertex v of G one can associate an ordered triplet (v(1), v(2), v(3)) with v(i) being a vertex of T-i(i = 1, 2, 3), such that the graph-theoretic distance between two vertices u, v of G equals the sum of respective tree-distances between u(i) and v(i). This labeling of the vertices of G can be obtained in O(n) time. As an application of this result we present an optimal O(Pt) time algorithm for computing the diameter of the graph G of a benzenoid system with n vertices.