Adjacency posets of planar graphs |
| |
Authors: | Stefan Felsner |
| |
Institution: | a Institut für Mathematik, Technische Universität Berlin, Strasse des 17. Juni 136, D-10623 Berlin, Germany b School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA |
| |
Abstract: | 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 poset 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 poset of a planar bipartite graph is at most 4. This result is best possible. More generally, the dimension of the adjacency poset of a graph is bounded as a function of its genus and so is the dimension of the vertex-face poset of such a graph. |
| |
Keywords: | Planar graph Adjacency poset Dimension Genus |
本文献已被 ScienceDirect 等数据库收录! |
|