论文标题
水平平面度的SPQR-TREE状嵌入表示形式
An SPQR-Tree-Like Embedding Representation for Level Planarity
论文作者
论文摘要
SPQR-TREE是一个数据结构，可有效地表示双连接平面图的所有平面嵌入。它是许多约束平面测试算法中的关键工具，该算法寻求按给定的一组约束的图形嵌入的平面嵌入。 我们开发了一个类似SPQR-Tree的数据结构，该数据结构代表具有单源的双连接级别图的所有级别平面嵌入，称为LP-Tree，并给出一个简单的算法以在线性时间计算它。此外，我们表明可以使用LP-Trees通过将它们用作SPQR-Trees的液位替代品来适应三种受约束的平面算法。
An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algorithms, which seek a planar embedding of a graph subject to some given set of constraints. We develop an SPQR-tree-like data structure that represents all level-planar embeddings of a biconnected level graph with a single source, called the LP-tree, and give a simple algorithm to compute it in linear time. Moreover, we show that LP-trees can be used to adapt three constrained planarity algorithms to the level-planar case by using them as a drop-in replacement for SPQR-trees.
