A printed circuit board needs more than a list of components and connections: components must be placed, and conductive tracks must be routed. A graph embedding gives an abstract graph a geometric layout by mapping vertices to points and edges to curves. The layout affects whether connections cross and how clearly the graph can be understood. section 15.0 section 15.5
In a 2-D embedding, distinct vertices occupy distinct positions, and an edge cannot pass through a vertex other than its endpoints. Edges may cross each other. If they do not, the embedding is planar; not every graph has one. An abstract graph can have many embeddings, with different numbers of crossings. section 15.1.2 section 15.2 section 15.5
For a straight-line drawing, build and assess an embedding incrementally:
- Assign each vertex a point in the drawing area; connect the endpoints of each edge with a segment. section 16.1.1
- Reject layouts with overlapping vertices or an edge passing through an unrelated vertex. For circular vertices, use center-to-center and vertex-to-segment distances. section 15.4.5 section 16.1.1
- Count edge crossings to compare valid layouts. For two segments, compute where their supporting lines meet, then check whether the intersection lies within both segments; shared endpoints need separate treatment. section 15.4.1 section 16.1.1
One baseline generates several random valid layouts and keeps the one with the fewest crossings. The shown validation checks pairs of vertices and each edge against every unrelated vertex; crossing counts check pairs of edges. Those loops take O(V² + VE + E²) checks per candidate, before accounting for repeated attempts. Better layouts may require a richer objective: short edges, separated vertices, and readable use of space matter too. Gradient descent and simulated annealing are explored as ways to optimize such layouts. section 16.1.1 section 16.5 section 17.3.2
Crossings are not the whole picture
Two drawings of the same graph can convey its structure very differently. Random placement can obscure the symmetry of a complete bipartite graph; a deliberate symmetric placement makes it easier to see. The objective is therefore a useful drawing, not merely a valid one. section 17.3.2
Embedding also appears in image search in a different sense: a feature extractor translates each image into a feature vector, and search compares vectors rather than images directly. The feature extractor is treated as a black box. Here the representation supports similarity search, whereas a graph embedding specifies a geometric drawing of vertices and edges. section 10.1.1 section 10.3.1 section 15.5
