On simultaneous planar graph embeddings

Peter Brass, Eowyn Cenek, Cristian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw and Joseph S.B. Mitchell
Computational Geometry
Volume 36, Issue 2 , February 2007, Pages 117-130
http://dx.doi.org/10.1016/j.comgeo.2006.05.006

WADS2003論文のジャーナル版．
同じ頂点数の2つの平面的グラフの埋め込みを与えるときに，2つのグラフの頂点を置く場所が同一になるようなものを考える．
そのような埋め込みはどのような場合に可能で，どのような場合に不可能なのだろうか？
まず，片方のグラフを埋め込んだら，もう片方の埋め込みも決まってしまう場合，すなわち，2つのグラフの頂点集合間の全単射が予め指定されている場合を考える．
この場合は，常に埋め込み可能であるとは限らないが，両方ともパスであったり，両方ともキャタピラであったり，いくつかの場合にはうまくいく．
そして，全単射が指定されていない場合には，例えば，両方とも外平面的グラフであってもうまくいく．
ただし，両方とも平面的グラフの場合にうまくいくのか，だめな場合があるのかは未解決のようである．
考えてる問題自体が面白い．