GRAPHS GENERATED BY FOUR CURVES IN THE PLANE
Andrey A. Dobrynin · 2008
Let G be a 4-regular planar graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly one cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Graphs of this class are called Grotzsch-Sachs graphs. Two infinite families of edge-4-critical Grotzsch-Sachs graphs generated by four curves in the plane have been announced in (4). In this paper, we present a complete proof of this result.