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 k-immersed in the plane if each edge is crossed by at most k other edges. By a proper k-immersion of a graph we mean a k-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 等数据库收录! |