Intersection Graphs in Simultaneous Embedding with Fixed Edges
Michael Jünger, Michael Schulz · Journal of Graph Algorithms and Applications · 2009
We examine the problem for two planar graphs G1 and G2 with the focus on their intersection S = G1∩G2. In particular, we will present the complete set of intersection graphs S that guarantee a for (G1,G2). More formally, we define the subset of all planar graphs as follows: A graph S lies in if every pair of planar graphs (G1, G2) with intersection S = G1∩G2 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.