Simultaneous embedding

In graph drawing and information visualization, simultaneous embedding is a technique for visualizing two or more different graphs on the same or overlapping sets of labeled vertices, while avoiding crossings within both graphs. Crossings between an edge of one graph and an edge of the other graph are allowed; it is only crossings between two edges of the same graph that are disallowed.

If edges are allowed to be drawn as polylines or curves, then any planar graph may be drawn without crossings with its vertices in arbitrary positions in the plane. Using the same vertex placement for two graphs provides a simultaneous embedding of the two graphs. Research in this type of simultaneous embedding has concentrated on finding drawings with few bends, or with few crossings between edges from the two graphs. Restricted models of simultaneous embedding have also been studied. In simultaneous geometric embedding, each graph must be drawn planarly with line segments representing its edges rather than more complex curves. In order to guarantee that such an embedding exists, one must restrict the two given graphs to subclasses of the planar graphs. In another restricted model of simultaneous embedding, simultaneous embedding with fixed edges, curves or bends are allowed in the edges but any edge that is present in both of the given graphs must be represented by the same curve in both drawings. When a simultaneous geometric embedding exists, it automatically is also a simultaneous embedding with fixed edges.

Simultaneous embedding is closely related to thickness, the minimum number of planar subgraphs that can cover all of the edges of a given graph, and geometric thickness, the minimum number of edge colors needed in a straight-line drawing of a given graph with no crossing between edges of the same color. In particular, the thickness of a given graph is two if the graph's edges can be partitioned into two subgraphs that have a simultaneous embedding, and the geometric thickness is two if the edges can be partitioned into two subgraphs that have a simultaneous geometric embedding.

For simultaneous embedding problems on more than two graphs, it is standard to assume that all pairs of input graphs have the same intersection as each other; that is, the edge and vertex sets of the graphs form a sunflower. This constraint is known as sunflower intersection.

...
Wikipedia