Planar embedding

As explained in Advanced Algorithms and Data Structures

A planar embedding is a representation of a graph in the plane in which vertices are distinct points and edges intersect only at shared endpoints.

A graph drawing is easier to follow when edges do not cross. A flow chart, for example, can be clear in one layout and confusing in another even though its vertices and edges are unchanged. A planar embedding is a crossing-free way to draw a graph in the plane. section 15.1

Represent each vertex by a distinct point in the plane and each edge by a non-self-intersecting curve between its endpoints. For the drawing to be a planar embedding, an edge must not pass through another vertex or intersect another edge, except at a shared endpoint. An abstract graph is planar if at least one such drawing exists. A drawing with crossings therefore does not, by itself, prove that the graph is non-planar. section 15.1.1 section 15.2.1

Try moving a vertex

A naïve drawing of the complete graph K4 appears to have crossing edges. Move one vertex past the crossing, and the same graph has a planar embedding. By contrast, neither K5 nor the complete bipartite graph K3,3 has one. section 15.2.1 section 15.1.1

Figure 15.8 Two embeddings for K4. Although it would seem like a good candidate for non-planarity, it’s enough to move one vertex around to find a planar embedding, as shown on the right.

Compare the two drawings of K4: changing the layout removes the apparent crossing without changing the graph. section 15.2.1

To decide whether a crossing-free layout is possible, use a planarity test rather than judging one drawing. Kuratowski’s theorem characterizes the obstruction through K5, K3,3, and subdivisions of those graphs. Algorithms can test planarity and return a planar embedding in linear time, though their implementations are complicated; a simpler approach may be more practical for small graphs. section 15.1.1 section 15.2.5

A planar embedding is a starting point for visualization, not a guarantee of a readable diagram. Keep adjacent vertices reasonably close, avoid winding edges, and preserve a useful sense of flow. When the graph is non-planar, crossings cannot all be eliminated; minimizing them is a different problem, and finding the minimum crossing number for a general graph is NP-complete. section 15.3 section 15.3.1

How Advanced Algorithms and Data Structures covers it

How deep it goes

Defines embeddings geometrically and contrasts them with planarity testing, while deferring the details of efficient algorithms.

Examples

Contrasts flow-chart layouts and uses K4, K5, and K3,3 to distinguish a poor drawing from a non-planar graph.

What it assumes

Assumes basic vertices-and-edges vocabulary while defining plane drawings and the curves used for edges.

What you can do after

Evaluate/understand whether crossings reflect a particular layout or an inherent limit of the graph.

How it connects

Connects planar embeddings to planar graphs, Kuratowski’s theorem, planarity testing, and crossing number.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

• embeddingkind of · A numerical vector representation of an item or input that encodes features or relationships useful for computational tasks.
• planarity testing algorithmproduced by · A planarity testing algorithm determines whether a graph can be embedded in the plane without edge crossings and may construct such an embedding.
• K3,3contrasts with · K3,3 is the complete bipartite graph whose two vertex partitions each contain three vertices.
• K5contrasts with · K5 is the complete graph on five vertices, with one edge connecting every pair of distinct vertices.
• crossing edgecontrasts with · A crossing edge is an edge in a graph drawing that intersects another edge at a point other than a shared endpoint.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.