
364 Simultaneous Embedding of Planar Graphs
11.4 Simultaneous Embedding
In the most restricted version of the problem, SGE, we insist that vertices are placed in
the same position, and edges must be straight-line segments. The SEFE setting relaxes the
straight-line condition but maintains that edges common to multiple graphs are realized
the same way in each. In the least restrictive setting, SE, we allow the same edge to be
realized differently in different graphs.
It has already been mentioned that simultaneous embedding of multiple graphs can be
thought of as a generalization of the notion of planarity. A classical result about planar
graphs connects ...