Abstrakt. Övergångsvinkeln för en rät linjedragning av en graf G = (V, E) är den minsta vinkeln mellan två korsningskanter i Γ. Bestämmer om en graf G har en rät linjeritning med en korsningsvinkel på 90 • är N P-hård [1]. Vi föreslår en enkel heurist för att beräkna en ritning med en stor korsningsvinkel. Den heuristiska girigt väljer den bästa positionen för en enda vertex i en slumpmässig uppsättning punkter. Algoritmen åtföljs av en hastighetshöjande teknik för att beräkna korsningsvinkeln för en rät linjeritning. Vi visar hur effektiv heurismen är i en omfattande empirisk utvärdering. Vår heurist var helt klart den vinnande algoritmen (CoffeeVM) i Graph Drawing Challenge 2017 [6].
Demel m.fl. (KIT) REF föreslår en girig heurist att välja den bästa positionen för en enda vertex från en slumpmässig uppsättning punkter.
A Greedy Heuristic for Crossing-Angle Maximization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}