Convex drawings of planar graphs and the order dimension of 3-polytopes

被引：74

作者：

Felsner, S ^{[1
]}

机构：

[1] Free Univ Berlin, Fachbereich Math & Informat, D-14195 Berlin, Germany

来源：

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 2001年 / 18卷 / 01期

关键词：

graph drawing; order dimension; Schnyder labeling;

D O I：

10.1023/A:1010604726900

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: . Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f-1)x(f-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.

引用

页码：19 / 37

页数：19

共 19 条

[1]

[Anonymous], 1948, Acta Sci. Math. Szeged, V11, P229

[2]

BREHM E, 2000, THESIS U BERLIN

[3] The order dimension of planar maps [J].

Brightwell, GR ;

Trotter, WT .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1997, 10 (04) :515-528

[4] Convex grid drawings of 3-connected planar graphs [J].

Chrobak, M ;

Kant, G .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1997, 7 (03) :211-223

[5]

FELSNER S, 2000, UNPUB J GRAPH THEORY

[6] Grid embedding of 4-connected plane graphs [J].

He, X .

DISCRETE & COMPUTATIONAL GEOMETRY, 1997, 17 (03) :339-358

[7]

Miller E, 1999, LECT NOTES COMPUT SC, V1719, P19

[8] ON THE ORDER DIMENSION OF CONVEX POLYTOPES [J].

REUTER, K .

EUROPEAN JOURNAL OF COMBINATORICS, 1990, 11 (01) :57-63

[9] RECTILINEAR PLANAR LAYOUTS AND BIPOLAR ORIENTATIONS OF PLANAR GRAPHS [J].

ROSENSTIEHL, P ;

TARJAN, RE .

DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (04) :343-353

[10]

SCHNYDER W, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P138

← 1 2 →