Vi presenterar en O(n 3/2 ) algoritm för att minimera antalet böjar i en ortogonal ritning av ett plan diagram. Det har länge funnits ett öppet problem i diagramritningen 2003, om gränsen mellan O(n 7/4 ε log n) som Garg och Tamassia visade 1996 skulle kunna förbättras. För att besvara denna fråga, visar vi hur man löser problemet med okapacitet min-kostnad flöde på en planar bidirected graf med begränsade kostnader och ansiktsstorlekar i O(n 3/2 ) tid.
Kärnan är en min-kostnadsflöde algoritm för att minimera antalet böjar i den andra fasen REF.
Accelerated bend minimization
{'venue': 'Lecture Notes in Computer Science', 'journal': 'Lecture Notes in Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}