×

Representations of planar graphs. (English) Zbl 0782.05026

Summary: 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. T. Tutte [Proc. Lond. Math. Soc., III. Ser. 13, 743-768 (1963; Zbl 0115.408)].

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
06A06 Partial orders, general

Citations:

Zbl 0115.408
PDFBibTeX XMLCite
Full Text: DOI