A labeling scheme for the gaps of the bridges of a broken cycle C′ of a biconnected graph G is developed. This labeling scheme incorporates the ideas of lexicographic order and of attachment order and is used to order the set of gaps (both proper gaps and cospan gaps) of all bridges of the broken cycle C′. Thus a linear order relation is induced on the set of gaps. An O(|V|+ |E|) algorithm for the construction of spanning forests for the bridge graph, Gc′, of the biconnected graph G = (V, E) with respect to the broken cycle C′ is given. As a bonus, this algorithm yields a set of instructions to produce a planar embedding of a biconnected graph, should one exist.
展开▼
机译：开发了一种用于双连通图G的断循环C'的桥梁间隙的标记方案。 该标签方案包含了词典顺序和附件订单的思想，用于订购破碎周期C'的所有桥梁的空隙（适当的间隙和COSPAN差距）。 因此，在一组间隙上引起线性顺序关系。 给出了关于桥梁曲线图，GC'的跨度森林的o（| v | + | e |）算法，用于相对于破碎的周期C'的双连通图G =（v，e）的跨越曲线图G =（v，e）。 作为一个奖励，该算法产生一组指令以产生平面嵌入的平面嵌入的是双连通图形，应该是一个。
展开▼
