Adjacency posets of planar graphs

被引：15

作者：

Felsner, Stefan ^{[1
]}

Li, Ching Man ^{[1
]}

Trotter, William T. ^{[2
]}

机构：

[1] Tech Univ Berlin, Inst Math, D-10623 Berlin, Germany

[2] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 05期

关键词：

Planar graph; Adjacency poset; Dimension; Genus; ORDER DIMENSION; SURFACES;

D O I：

10.1016/j.disc.2009.11.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we show that the dimension of the adjacency poset of a planar graph is at most 8. From below, we show that there is a planar graph whose adjacency poser has dimension 5. We then show that the dimension of the adjacency poset of an outerplanar graph is at most 5. From below, we show that there is an outerplanar graph whose adjacency poset has dimension 4. We also show that the dimension of the adjacency poser of a planar bipartite graph is at most 4. This result is best possible. More generally, the dimension of the adjacency poser of a graph is bounded as a function of its genus and so is the dimension of the vertex-face poser of such a graph. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：1097 / 1104

页数：8

共 16 条

[1]

ALBERTSON MO, 1978, GLASG MATH J, V9, P163

[2] On acyclic colorings of graphs on surfaces [J].

Alon, N ;

Mohar, B ;

Sanders, DP .

ISRAEL JOURNAL OF MATHEMATICS, 1996, 94 :273-283

[3]

[Anonymous], 1992, Combinatorics and Partially Ordered Sets: Dimension Theory

[4]

BOGART KP, 1976, DISCRETE MATH, V16, P71

[5] THE ORDER DIMENSION OF CONVEX POLYTOPES [J].

BRIGHTWELL, G ;

TROTTER, WT .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (02) :230-245

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

Brightwell, GR ;

Trotter, WT .

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

[7] Dimension, graph and hypergraph coloring [J].

Felsner, S ;

Trotter, WT .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2000, 17 (02) :167-177

[8] Geodesic embeddings and planar graphs [J].

Felsner, S .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2003, 20 (02) :135-150

[9] Convex drawings of planar graphs and the order dimension of 3-polytopes [J].

Felsner, S .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2001, 18 (01) :19-37

[10] 3-INTERVAL IRREDUCIBLE PARTIALLY ORDERED SETS [J].

FELSNER, S .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1994, 11 (02) :97-125

← 1 2 →