We prove that every graph of rank-width $k$ is a pivot-minor
of a graph of tree-width at most $2k$ and every graph of linear rank-width $k$ is
a pivot-minor of a graph of path-width at most $k+1$.
We also prove that graphs of rank-width
at most $1$ are exactly vertex-minors of trees, and graphs of linear rank-width
at most $1$ are precisely vertex-minors of paths. In addition, we show that
bipartite graphs of rank-width at most $1$ are exactly pivot-minors of trees
and bipartite graphs of linear rank-width at most $1$ are precisely
pivot-minors of paths.
Also, we calculate the linear rank-width of complete binary trees. And we show that if a tree has linear rank-width at least $k$, then it has the complete binary tree of height $k$ as a vertex-minor. Finally, we describe an interesting question that a class of graphs with unbounded linear rank-width contains all trees as vertex-minors or pivot-minors. We prove that this question for pivot-minor is false and we suggest another version of the question.
Tree-width가 $k$인 그래프는 rank-width가 $k+1$ 이하임이 알려져 있었지만, rank-width가 작은 그래프에 대해서는 tree-width와 관련된 결과가 없었다. 3장에서 우리는 처음으로 rank-width가 $k$ 이하인 그래프는 tree-width가 $2k$인 그래프의 pivot-minor로 얻을 수 있음을 증명하였고, 또한 linear rank-width가 $k$ 이하인 그래프는 path-width가 $k+1$인 그래프의 pivot-minor로서 얻을 수 있음을 증명하였다. 이 증명의 보조정리로서 rank-width가 $1$인 그래프는 정확히 트리의 vertex-minor들이고 linear rank-width가 $1$인 그래프는 정확히 패쓰의 vertex-minor들임을 증명하였다. 그리고 그래프들이 이분 그래프이면, 이 보조정리들의 vertex-minor를 pivot-minor로 대체할 수 있음을 보였다.
4장에서는, 높이가 $k$인 완전 이진 트리들과 그들의 결합 그래프들의 linear rank-width를 계산하였다. 또한 트리가 linear rank-width가 $k$보다 크면 높이가 $k$인 완전 이진 트리들을 vertex-minor로서 가짐을 증명하였다.
5장에서는, 우리는 그래프가 linear rank-width가 어떤 수 이상이면 반드시 어떤 그래프를 vertex-minor 혹은 pivot-minor로서 가진다는 문제에 대해서 생각해보았다. 처음에는 유명한 Robertson과 Seymour의 path-width 정리처럼 문제의 어떤 그래프가 트리가 될 것이라고 추측을 하였다. 하지만, pivot-minor에 대해서는 이 추측이 잘못 되었다는 사실을 증명하였고, 트리를 대신하여 트리의 결합 그래프가 어떤 그래프에 들어갈 것이라고 문제를 제시하였다.
