Planar Graphs, An Introduction

Introduction

For most applications, the geometric representation of a graph as points and connecting edges is merely a convenient representation. The topology (e.g. the number of spacial dimensions, edge intersections, etc) is usually ignored. The connections carry the information. However, when a graph corresponds to physical entities with geometric properties, its topology becomes important.

A graph is "embedded" in a manifold when its vertices and edges are entirely contained in the manifold, so that no two edges intersect. Also, no edge may intersect itself, or any vertices.

For example, a set of interconnected electronic components on a printed circuit board can be modeled by a graph embedded in the plane. Each component is a vertex, each connecting wire an edge. If the wires cross, that's a short circuit, so you really want a proper embedding.

In another application, an embedded graph represents countries on a globe. Each vertex is a region and each edge represents a shared border. Regions joined at a single point are not considered adjacent. Colorado is adjacent to Utah, but not Arizona. Every world map corresponds to an embedded spherical graph, where connected vertices represent neighboring regions.