论文标题
具有广义端口约束的无向图的分层图
Layered Drawing of Undirected Graphs with Generalized Port Constraints
论文作者
论文摘要
这项研究的目的是绘制复杂机器的电缆计划的实用方法。这样的计划由连接组件特定端口的电子组件和电缆组成。由于计算机是分别为每个客户端配置的，因此需要自动绘制电缆计划。这些图纸必须可以很好地阅读，以便技术人员可以使用它们来调试机器。为了建模插头插座，我们介绍端口组；在一个组中，端口可以更改其位置（我们用来改善布局的美学），但是组的端口必须形成一个连续的块。 我们通过扩展众所周知的Sugiyama框架来解决此类有线计划的问题，以便它结合了端口和端口组。由于该框架假定有针对性的图形，因此我们提出了几种方法来定义给定无向图的边缘。我们在实验中对这些方法进行了对实际数据和合成数据的实验比较，这些数据仔细模拟了现实世界数据。我们通过计数弯曲和交叉点来测量所得图的美学。使用这些指标，我们通过实验将我们的方法与Kieler [JVLC 2014]进行比较，这是一个在端口约束存在下绘制图的库。我们的方法产生的杂交量减少了10--30％，而在弯曲的数量和计算图纸的时间方面，它的性能却比基埃尔（Kieler）差得多或稍差。
The aim of this research is a practical method to draw cable plans of complex machines. Such plans consist of electronic components and cables connecting specific ports of the components. Since the machines are configured for each client individually, cable plans need to be drawn automatically. The drawings must be well readable so that technicians can use them to debug the machines. In order to model plug sockets, we introduce port groups; within a group, ports can change their position (which we use to improve the aesthetics of the layout), but together the ports of a group must form a contiguous block. We approach the problem of drawing such cable plans by extending the well-known Sugiyama framework such that it incorporates ports and port groups. Since the framework assumes directed graphs, we propose several ways to orient the edges of the given undirected graph. We compare these methods experimentally, both on real-world data and synthetic data that carefully simulates real-world data. We measure the aesthetics of the resulting drawings by counting bends and crossings. Using these metrics, we experimentally compare our approach to Kieler [JVLC 2014], a library for drawing graphs in the presence of port constraints. Our method produced 10--30 % fewer crossings, while it performed equally well or slightly worse than Kieler with respect to the number of bends and the time used to compute a drawing.
