Representations of Planar Graphs

Authors:
  • GBGraham R. Brightwell
    Graham R. Brightwell
  • ESEdward R. Scheinerman
    Edward R. Scheinerman
Publisher website
Google Scholar
Abstract
This paper shows that every 3-connected planar graph G can be represented as a collection of circles, one circle representing each vertex and each face, so that, for each edge of G, the four circles representing the two endpoints and the two neighboring faces meet at a point, and furthermore the vertex-circles cross the face-circles at right angles. This extends a result of W. Thurston [The Geometry and Topology of Three Manifolds, unpublished] and, independently, Andreev. From this we deduce two corollaries: (1) The partial order formed by taking the vertices, edges, and bounded faces of G, ordered by inclusion, is a circle order; (2) One can represent G and its dual simultaneously in the plane with straight-line edges so that the edges of G cross the dual edges at right angles. This answers a question first asked by W. Tutte [Proc. LMS, 13 (3) (1963), pp. 743–768].

This publication has 12 references indexed in Scilit: