Graphs and Circle-Systems

We will explain some fundamentals on graphs, including planar graphs and Euler’s formula. As a representation of a graph by a circle-system, we consider first the orthogonal-circle representation (abbreviated as OCR) of a special type of graphs, called quadrangulations. An OCR of a graph is a circle-system consisting of circles each corresponding to a vertex of the graph, in which each pair of circles corresponding to a pair of adjacent vertices is orthogonally crossing, whereas each pair of circles corresponding to non-adjacent vertices do not cross each other. The OCR theorem gives a necessary and sufficient condition for a quadrangulation to have an OCR. From the OCR theorem, the coin graph theorem (also called Koebe’s theorem, or the Koebe-Andreev-Thurston theorem) and Steinitz’ theorem characterizing the polyhedral graphs, are derived easily.