Unit-Length Embedding of Binary Trees on a Square Grid
を読んだ。
先行研究のミスを指摘していてワロタ。
概要
二分木をsquare gridに埋め込めるかどうかはNP-Complete
最大次数に注目すると、最大次数2のグラフはサイクルまたはパスグラフなので、埋め込みは自明に可能
最大次数を3に許容すると二分木となるが、この場合不可能であることが示されたのでギャップになっている
証明のテクは、正方形サイズの二分木で、一意な埋め込みがあるものを見つけ、あとはおなじみのlogic engineで証明する
このグラフはU-Treeと呼ばれ、一意な埋め込みをもつっぽい。
あとは、extended skeletonをこれで置き換えて構築し（そのままでは次数４の頂点があるのでうまく置き換える）、似たようなことをやる
これはいつものskeleton
感想
最大次数を3まで許容してしまうと二分木が許されるのがやばい。二分木は、ルートからの距離に比例してノード数が指数的に増えるが、一般の次元グリッドは、ある点からのマンハッタン距離に対してノード数は多項式なので、明らかに任意の二分木を埋め込むことは不可能。
直感的には、どんなに対しても、ある程度のサイズの二分木が存在して、一位に埋め込むことができそうで、あとは似たようにlogic engineを修正すれば埋め込みのNP-Completenessを示すことができそう。これはsquareグリッドに限らず、任意のパターンでおｋ
かなり汎用的なテクでびっくりしてしまう。
これ論文になるん？
