Journal of Graph Algorithms and Applications Intersection Graphs in Simultaneous Embedding with Fixed Edges
Journal of Graph Algorithms and Applications Intersection Graphs in Simultaneous Embedding with Fixed Edges
复制标题
图算法与应用杂志 固定边同时嵌入中的相交图
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
M. Schulz
中科院分区：
文献类型：
--
作者：
M. Jünger;M. Schulz;S. Kobourov;M. Jünger;M. Schulz
研究了两个平面图G1和G2的固定边同时嵌入问题，重点是它们的交集S = G1 <$G2。特别地，我们将给出保证（G1，G2）的固定边同时嵌入的交图S的完整集合。更正式地说，我们定义所有平面图的子集I SEFE如下：一个图S位于I SEFE中，如果每对相交的平面图（G1，G2）有一个固定边的同时嵌入。我们将通过对拓扑嵌入的详细研究来刻画这一集合，最后给出这一集合中的图的完整列表，作为本文的主要结果。
We examine the simultaneous embedding with fixed edges 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 simultaneous embedding with fixed edges for (G1, G2). More formally, we define the subset I SEFE of all planar graphs as follows: A graph S lies in I SEFE if every pair of planar graphs (G1, G2) with intersection S = G1 ∩ G2 has a simultaneous embedding with fixed edges. 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.