Intersection Graphs in Simultaneous Embedding with Fixed Edges

Abstract

We examine the problem for two planar graphs G₁ and G₂ with the focus on their intersection S = G₁∩G₂. In particular, we will present the complete set of intersection graphs S that guarantee a for (G₁,G₂). More formally, we define the subset of all planar graphs as follows: A graph S lies in if every pair of planar graphs (G₁, G₂) with intersection S = G₁∩G₂ has a . We will characterize this set by a detailed study of topological embeddings and finally give a complete list of graphs in this set as our main result of this paper.