{'fraction_non_alphanumeric': 0.02502844141069397, 'fraction_numerical': 0.0022753128555176336, 'mean_word_length': 4.365853658536586, '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}}
Improved approximations of crossings in graph drawings

We give improved approximations for two classical embedcling problems: (i) minimizing the number of crossings in a drawing of a bounded degree graph on the plane; and (ii) minimizing the VLSI layout area of a degree four graph. These improved algorithms can be applied to improve a variety of VLSI layout problems. Our results are as follows. (i) We compute a drawing on the plane of a bounded degree graph in which the sum of the numbers of vertices and crossings is O(log a n) times the optimal minimum sum. This is a logarithmic factor improvement relative to the best known result. (ii) We compute a VLSI layout of a degree four graph in a grid with constant aspect ratio the area of which is O(log 4 n I times the optimal minimum layout area. This is an O(log 2 n) improvement over the best known long standing result.