首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号