格子圖書式嵌入的型數

Abstract

在 一 個 把 圖 嵌 入 成 $p$ 頁 的 書 式 嵌 入 中, 我 們 定義 一 個 點 的 型 態 為 如 下 的 $p \times 2$ 矩 陣 \[ \begin{array}{c} \tau (v)\\ \end{array} = \left[ \begin{array}{cc} l_{v,1}&r_{v,1}\\ \vdots & \vdots \\ l_{v, p}&r_{v,p}\\ \end{array} \right], \] $l_{v,i}$ $($或 $r_{v,i})$ 是 這 個 點 在 第 $i$ 頁 往 左 (右)所 連 的 邊 的 個 數. 一 個 圖 $G$ 的 型 數, $T(G)$, 是 這 個圖 所 有 的 書 式 嵌 入 中 所 得 到 最 少 的 點 型 態.在 這 篇 論 文 中, 我 們 將 討 論 型 數 的 一 般 性 質 以 及 某些 特 殊 圖 型 的 型 數. 最 主 要 的, 我 們 找 到 格 子 圖 $(L_{m,n})$ 型 數 的 上 界. 在 $m\le 3$ 時, 我 們 給 予 了 $L_{2,n}$, $L_{3,n}$ 型 數 的 正 確 值. 在 $m=2$ 的 時 候,我 們 推 翻 了 J. Buss 等 人 對 於 $L_{2,n}$ 的 型 數 在 $n\ge 4$ 時 不 會 比 5 小 的 猜 測. The $type$ of a vertex $v$ in a $p$-page book-embedding is the $p\times 2$ matrix of nonnegative integers \[ \begin{array}{c} \tau (v)\\ \end{array} = \left[ \begin{array}{cc} l_{v,1}& r_{v,1}\\ \vdots & \vdots \\ l_{v,p}&r_{v,p}\\ \end{array} \ right], \] where $l_{v,i}$(respectively, $r_{v,i}$) is the number of edges incident to $v$ that connect on page $i$ to vertices lying to the left (respectively, to the right) of $v$. The $ typenumber $ of a graph $G,$ $T(G)$, is the minimum number of different types among all the book-embeddings of G. In this thesis, we shall consider the general properties of $typenumber$ and the $typenumber$ of some specific graphs. Mainly, we find an upper bound for lattice graph, $L_{m,n}$, and give exact solutions when $m\le 3$. In case that $m=2$ and $n\geq 3$, our result disprove the conjecture by J. Buss et.al. which says for $n\ge 4$, $T(L_{2,n})$ is not less than 5.