{'fraction_non_alphanumeric': 0.04335260115606936, 'fraction_numerical': 0.011560693641618497, 'mean_word_length': 3.880281690140845, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards an Optimal Algorithm for Recognizing Laman Graphs

A graph G with n vertices and m edges is a Laman graph, or equivalently a generically minimally rigid graph, if m = 2n - 3 and every induced subset of k vertices spans at most 2k - 3 edges. Laman graphs play a fundamental role in rigidity theory. We discuss the Verification problem: Given a graph G with n vertices, decide if it is Laman. We present an algorithm that recognizes Laman graphs in O(Tst(n) + n log n) time, where Tst(n) is the best time to extract two edge disjoint spanning trees from a graph with n vertices and 2n - 2 edges, or decide no such trees exist. So far, it is known that Tst(n) is O(n3/2/spl radic/log n).