A planar map is a planar graph together with a fixed embedding in the sphere, considered up to orientation-preserving homeomorphism. A rooted planar map has a distinguished oriented edge, which removes most embedding symmetries.
A face of a planar map is a connected component of the complement of its embedded graph. Its degree is the number of edge incidences around its boundary, counted with multiplicity, and the sum of all face degrees is twice the number of edges.
A rooted planar map is a planar map with a distinguished oriented edge called its root edge. Its tail is the root vertex, and the face on a chosen side of the edge may be designated as the root face.
A planar quadrangulation is a planar map in which every face has degree four, with incidences counted with multiplicity. A pointed quadrangulation additionally has a distinguished vertex.
A squaregraph has separate conditions on bounded faces and interior vertex degrees; its outer face need not be quadrilateral.
The trivial bijection sends a rooted planar map with edges to a rooted planar quadrangulation with faces. Put one new vertex in each face and, in each corner, connect that face vertex to the incident original vertex. Each original edge then lies inside one quadrangular face; deleting the original edges gives the quadrangulation. The face bipartition recovers the original vertices and hence the inverse map.
Articles by others on the same topic
There are currently no matching articles.