Planarity and Edge Poset Dimension
Planarity and Edge Poset Dimension
复制标题
DOI：
10.1006/eujc.1996.0064
复制
发表时间：
1996-11
期刊：
影响因子：
--
通讯作者：
H. D. Fraysseix;P. D. Mendez
中科院分区：
文献类型：
--
作者：
H. D. Fraysseix;P. D. Mendez
摘要平面图在离散数学的不同领域有着不同的刻画。平面性用拓扑学、组合学、代数或搜索树来表示。最近，Schnyder的工作将平面性与偏序理论联系起来。无圈定向和相关的边偏序导致了平面图的一个新的特征，它也描述了所有可能的平面嵌入。本文证明了双极平面有向图与二维无N偏序之间存在一个双射.我们还给出了平面性的2-可着色图的一个特征，并提供了一个简短的证明以前的结果平面格。
Abstract Different areas of discrete mathematics lead to instrinsically different characterizations of planar graphs. Planarity is expressed in terms of topology, combinatorics, algebra or search trees. More recently, Schnyder's work has related planarity to partial order theory. Acyclic orientations and associated edge partial orders lead to a new characterization of planar graphs, which also describes all of the possible planar embeddings. We prove here that there is a bijection between bipolar plane digraphs and 2-dimensional N- free partial orders. We give also a characterization of planarity in terms of 2-colorability of a graph and provide a short proof of a previous result on planar lattices.