2007/11/19 by Sergey Bereg, Bereg, Sergey
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #Structural Analysis and Optimization #cs.CG
paper · pdf · doi:10.48550/arxiv.0711.2835
openalex publication_date 2007/11/19 · arxiv created 2008/02/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n2) 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(nlog n). The total running time can be reduced O(n√(nlog 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.