Abstract Traditionellt är kvaliteten på ortogonala planritningar kvantifieras antingen av det totala antalet kurvor, eller det maximala antalet kurvor per kant. Detta försummar dock att i typiska tillämpningar, kanter har varierande betydelse. I detta arbete undersöker vi ett tillvägagångssätt som gör det möjligt att ange maximalt antal böjar för varje kant individuellt, beroende på dess betydelse. Vi anser att ett nytt problem som kallas FLEXDRAW definieras enligt följande. Med tanke på en planar graf G = (V, E) på n hörn med maximal grad 4 och en funktion flex : E −→ N 0 som tilldelar en flexibilitet till varje kant, erkänner G en planar inbäddning på rutnätet så att varje kant e har som mest flex (e) böjar? Observera att i vår miljö är kombinatoriska inbäddning av G inte fast. FLEXDRAW utökar direkt problemet β-bäddbarhet frågar om G kan inbäddas med högst β böjar per kant. Vi ger en algoritm med drifttid O(n 2 ) lösa FLEXDRAW när flexibiliteten i varje kant är positiv. Detta inkluderar 1-bäddbarhet som ett specialfall och därmed minskar komplexitetsgapet mellan 0-bäddbarhet, som är N P-hård att bestämma, och 2-bäddbarhet, som är effektivt lösbar eftersom varje plana graf med maximal grad 4 medger en 2-bädd med undantag för oktahedron. Förutom polynom-tidsalgoritmen visar vi att FLEXDRAW är N P-hård även om kanterna med flexibilitet 0 framkallar ett träd eller en förening av delade stjärnor.
Å andra sidan, inte alla 4-plans grafer medger ortogonala ritningar med en böj per kant; dock, testa om en 4-plans graf medger en sådan ritning kan göras i polynom tid REF.
Orthogonal Graph Drawing with Flexibility Constraints
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}