Article ID Journal Published Year Pages File Type
4647622 Discrete Mathematics 2013 14 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,