We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. We present positive and negative results for the two versions of the problem. Among the positive results with given mapping, we show that we can embed two paths on an n x n grid, and two caterpillar graphs on a 3n x 3n grid. Among the negative results with given mapping, we show that it is not always possible to simultaneously embed three paths or two general planar graphs. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n) x O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n(2)) x O(n(2)) grid. (c) 2006 Elsevier B.V. All rights reserved.
展开▼
机译：我们考虑同时嵌入平面图的问题。此问题有两种变体，一种是给出两个图的顶点之间的映射，另一种是不给出映射。我们针对该问题的两个版本给出了正面和负面的结果。在给定映射的积极结果中，我们表明我们可以在n x n网格上嵌入两条路径，在3n x 3n网格上嵌入两个毛虫图。在给定映射的负面结果中，我们表明并非总是可能同时嵌入三个路径或两个一般平面图。如果未给出映射，则表明可以在O（n）x O（n）网格上同时嵌入任意数量的外平面图，并且可以在O（n（2（2））上同时嵌入外平面图和普通平面图。 ））x O（n（2））网格。 （c）2006 Elsevier B.V.保留所有权利。
展开▼
