Right Angle Crossing (RAC) ritningar är polyline ritningar där varje korsning bildar fyra rätvinklar. RAC-ritningar har införts eftersom kognitiva experiment har visat att ett ökat antal korsningar inte minskar läsbarheten hos en ritning om kanterna korsas i rät vinkel. Vi undersöker i vilken utsträckning RAC-ritningar kan bidra till att övervinna begränsningarna i allmänt antagna planar grafritningskonventioner, vilket ger både positiva och negativa resultat. För det första bevisar vi att det finns acykliska planritningar som inte medger någon rät linje uppåt RAC-ritning och att motsvarande beslutsproblem är NP-hårda. Vi visar också digrafer vars rät linje uppåt RAC-ritningar kräver exponentiellt område. Genom att utnyttja de tekniker som införts för att studera rät linje uppåt RAC-ritningar, visar vi också att det finns planar oriktade grafer som kräver kvadratiska områden i varje rät linje RAC-ritning. För det andra studerar vi om RAC-ritningar gör det möjligt för oss att rita avgränsade grafer med lägre kurv komplexitet än den som krävs av mer begränsade ritkonventioner. Vi bevisar att varje graf med vertexgrade högst sex (som mest tre) medger en RAC-ritning med kurv komplexitet två (resp. Ett) och med kvadratiskt område. För det tredje, vi anser en naturlig icke-planar generalisering av planar inbäddade grafer. Här ger vi gränser för kurv komplexitet och område skiljer sig från de som är kända för planar inbäddningar.
Angelini m.fl. REF visade att problemet med att avgöra om en acyklisk planritning medger en rät linje uppåt RAC-ritning är N P-hård.
On the Perspectives Opened by Right Angle Crossing Drawings
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}