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


Proper 1-immersions of graphs triangulating the plane
Authors:Vladimir P Korzhik
Institution:National University of Chernivtsi, Chernivtsi, Ukraine; Institute of Applied Problems of Mechanics and Mathematics of National Academy of Science of Ukraine, Lviv, Ukraine
Abstract:In this paper we study what planar graphs are “rigid” enough such that they can not be drawn on the plane with few (1, 2, or 3) crossings per edge. A graph drawn on the plane is kk-immersed in the plane if each edge is crossed by at most kk other edges. By a proper  kk-immersion of a graph we mean a kk-immersion of the graph in the plane such that there is at least one crossing point. We give a characterization (in terms of forbidden subgraphs) of 4-connected graphs which triangulate the plane and have a proper 1-immersion. We show that every planar graph has a proper 3-immersion.
Keywords:Topological graph  Crossing edges  1-planar graph  1-immersion
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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