  In [1], a new construction called red-black hierarchy characterizing Laman
graphs and an algorithm for computing it were presented. For a Laman graph
G=(V,E) with n vertices it runs in O(n^2) time assuming that a partition of
(V,E+e) into two spanning trees is given. We show that a simple modification
reduces the running time to O(n\log n). The total running time can be reduced
O(n\sqrt{n\log n}) using the algorithm by Gabow and Westermann [2] for
partitioning a graph into two forests. The existence of a red-black hierarchy
is a necessary and sufficient condition for a graph to be a Laman graph. The
algorithm for constructing a red-black hierarchy can be then modified to
recognize Laman graphs in the same time.
