论文标题
在正式图纸中用于弯曲最小化的整数线性程序
An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings
论文作者
论文摘要
正式网格通过同心圆和圆圈中心发出的直线辐条来描述。正式图是正交绘图的类似物。这样的图纸具有无限的外表面和一个包含原点的中央面。我们以正义表示的概念为基础（Barth等，SocG，2017年），我们描述了一个整数线性程序（ILP），用于计算具有给定的嵌入式和固定外部和中央面的无弯曲正式表示。使用ILP作为构建块，我们介绍了一种修剪技术，以使用给定的嵌入式和固定的外表面，但可以自由选择的中央面，计算弯曲最佳的正式图纸。我们的实验表明，与正交图纸相比，使用相同的嵌入和相同的外表面相比，使用正式图纸平均将弯曲的数量减少了43.8％。此外，我们的方法使我们能够在几秒钟内计算嵌入式图的正式图纸，例如北京的地铁系统或伦敦。
An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.
