以两层图绘制的两层图画分割的顶点 (Splitting Vertices in 2-Layer Graph Drawings)

Reyan Ahmed,Patrizio Angelini,Michael A. Bekos,Giuseppe Di Battista,Michael Kaufmann,Philipp Kindermann,Stephen Kobourov,Martin Nöllenburg,Antonios Symvonis,Anaïs Villedieu,Markus Wallinger

Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two sets of entities (vertices) are placed on two parallel lines (layers), and their relationships (edges) are represented by segments connecting vertices. Methods for constructing 2-layer drawings often try to minimize the number of edge crossings. We use vertex splitting to reduce the number of crossings, by replacing selected vertices on one layer by two (or more) copies and suitably distributing their incident edges among these copies. We study several optimization problems related to vertex splits to minimize the number of crossings. While we prove that some variants are NP-complete, we obtain polynomial-time algorithms for others. We run our algorithms on a benchmark set of bipartite graphs representing the relationships between human anatomical structures and cell types.

翻译：双部分图案建构两组不同实体在多个应用程序中的关系模式,这些实体自然被画成两层图画。在这样的图画中,两组实体(脊椎)被放在两条平行线上(层),两组实体(边缘)的关系由连接脊椎的部位代表。建造两层图的方法往往试图尽量减少边缘过境点的数量。我们使用顶点分割来减少过境点的数量,将一个层上选定的脊椎替换为两个(或更多)副本,并在这些拷贝中适当分配其事件边缘。我们研究了与脊椎分割有关的几个优化问题,以尽量减少跨越次数。虽然我们证明有些变量是NP的完整,但我们为其他人获得了多层时算法。我们用一组双部分图谱来计算我们的算法,这些图谱是代表人类解剖结构和细胞类型之间的关系。