グラフ書き換え言語LMNtalは、様々なグラフ構造を簡潔に扱うことが出来るプログラミング言語である。LMNtalにおける型付けとして、グラフの生成規則をもとに型付けを行うLMNtal ShapeTypeが提案されている。LMNtal ShapeTypeにおけるグラフ型は、素朴には生成規則の逆実行により検査可能であるが、一般には効率が十分ではないという課題がある。本論文では、この課題を解決するため、token passingを用いたグラフ型検査手法を提案し、グラフの生成規則からの変換アルゴリズムを示す。本手法に基づく型検査を採用することにより、従来の型検査と比べ、状態空間が削減されることを確認した。