BIPOLAR ORIENTATIONS REVISITED

被引：45

作者：

DEFRAYSSEIX, H

DEMENDEZ, PO

ROSENSTIEHL, P

机构：

[1] CNRS, EHESS, 75006 Paris

来源：

DISCRETE APPLIED MATHEMATICS | 1995年 / 56卷 / 2-3期

关键词：

D O I：

10.1016/0166-218X(94)00085-R

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Acyclic orientations with exactly one source and one sink - the so-called bipolar orientations - arise in many graph algorithms and specially in graph drawing. The fundamental properties of these orientations are explored in terms of circuits, cocircuits and also in terms of ''angles'' in the planar case. Classical results get here new simple proofs; new results concern the extension of partial orientations, exhaustive enumerations, the existence of deletable and contractable edges, and continuous transitions between bipolar orientations.

引用

页码：157 / 179

页数：23