Abstrakt. Det riktade lagerproblemet (DLP) löser ett steg i den allmänt använda lagerbaserade metoden för att automatiskt rita riktade acykliska grafer. För att tillgodose cykliska grafer används vanligtvis ett förbehandlingssteg som löser problemet med Feedback Arc Set (FASP) för att göra grafen acyklisk innan en skiktning bestäms. Här presenterar vi det Generalized Layering Problem (GLP), som löser kombinationen av DLP och FASP samtidigt, vilket tillåter allmänna grafer som ingång. Vi presenterar ett heltal programmering modell och en heuristic för att lösa NP-fullständig GLP och utföra noggranna utvärderingar på olika uppsättningar grafer och med olika implementationer för stegen i den skiktbaserade metoden. Vi observerar att GLP minskar antalet overksamma noder avsevärt, kan producera mer kompakta ritningar, och förbättrar på grafer där DLP ger dåliga proportioner.
Rüegg m.fl. REF integrerar de två första faserna i tillvägagångssättet Sugiyama för att tillåta godtyckliga grafer som indata genom att minimera en viktad summa av antalet omvända bågar och antalet overksamma hörn.
A Generalization of the Directed Graph Layering Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}