Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Intersection Graphs in Simultaneous Embedding with Fixed Edges
Vol. 13, no. 2, pp. 205-218, 2009. Regular paper.
Abstract 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.
Submitted: March 2009.
Reviewed: June 2009.
Revised: July 2009.
Accepted: July 2009.
Final: July 2009.
Published: July 2009.
Communicated by Stephen G. Kobourov