Adjacency posets of planar graphs

作者：Felsner Stefan^*; Li Ching Man; Trotter William T

来源：Discrete Mathematics, 2010, 310(5): 1097-1104.

DOI：10.1016/j.disc.2009.11.005

• Planar graph
• Adjacency poset
• Dimension
• Genus

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.

• 出版日期2010-3-6