论文标题
大双连接图的示意图
Schematic Representation of Large Biconnected Graphs
论文作者
论文摘要
假设给出了一个双连接的图，由大型组件以及其他几个较小的组件组成，每个组件通过分离对与主组件分开。我们研究了该图的结构的示意图的存在和计算时间，其中主组件被绘制为磁盘，与分离对的顶点是磁盘边界上的点，小部分是磁盘的边界上的点，并且将小部分放置在磁盘外部，并将其表示为无连接的lunes连接其分离对的圆锥。我们根据不同的方法来考虑这种示意图表示的几种图形惯例，以说明小组件的大小。我们将测试存在此类表示的问题绘制为测试适当约束的$ 1 $ PAGE图书 - 账簿上的一个测试之一，并提出了几种多项式时间算法。
Suppose that a biconnected graph is given, consisting of a large component plus several other smaller components, each separated from the main component by a separation pair. We investigate the existence and the computation time of schematic representations of the structure of such a graph where the main component is drawn as a disk, the vertices that take part in separation pairs are points on the boundary of the disk, and the small components are placed outside the disk and are represented as non-intersecting lunes connecting their separation pairs. We consider several drawing conventions for such schematic representations, according to different ways to account for the size of the small components. We map the problem of testing for the existence of such representations to the one of testing for the existence of suitably constrained $1$-page book-embeddings and propose several polynomial-time algorithms.
