论文标题
低度的RAC图纸
RAC Drawings of Graphs with Low Degree
论文作者
论文摘要
由认知实验的激励，提供证据表明大型交叉角度不会损害图形图的可读性，RAC（直角交叉）图纸被引入以解决非平面图可读表示的问题，通过支持所有交叉形式的最佳案例，其中所有交叉形式构成90°角。在这项工作中，我们在寻找低度图的RAC图纸方面取得了进展。在这种情况下，一个长期的开放问题询问所有3级图3的图形是否都允许直线RAC图纸。对于哈密顿学位3的图表，这个问题已得到积极回答。我们通过扩展到3 edge-colorable Leg-3图的类别来改进结果。当允许每个边缘具有一个弯曲时，我们证明了4级图形的RAC绘图，这是以前仅以Leger-3图所知的结果。最后，我们表明，7-边色的7级图形录入了RAC图纸，每个边缘有两个弯曲。这改善了先前的6级图。
Motivated by cognitive experiments providing evidence that large crossing-angles do not impair the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90° angles. In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs.
