Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes
Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes
复制标题
DOI：
10.1023/a:1010604726900
复制
发表时间：
2001-03
期刊：
影响因子：
--
通讯作者：
S. Felsner
中科院分区：
文献类型：
--
作者：
S. Felsner
我们定义了3-连通平面图的一个类似的树分解。在此基础上，我们得到：设G是一个3连通平面图，则G有一个凸图，其顶点嵌入在（1）（1）格上.设G是一个3连通平面图。图G的顶点、边和有界面的关联序的维数至多为3。第二个结果最初是由于Brightwell和Trotter。这里我们给出一个简单得多的证明。
We define an analogue of Ëchnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with faces, then G has a convex drawing with its vertices embedded on the (1)¢( 1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3. The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.