第一章 问题与背景 1
§1．1 问题的由来 1
§1．2 图的一些基本知识 3
§1．3 纵横嵌入 6
§1．4 极大极小设计 11
§1．5 最少孔道设计 13
§1．6 最小面积设计 14
§1．7 定位与布线 15
§1．8 纵横分解 17
§1．9 注记 19
§2．1 图的定向 21
第二章 一般嵌入 21
§2．2 确向术 26
§2．3 平面性判定 30
§2．4 平面嵌入 33
§2．5 平面嵌入的数目 39
§2．6 注记 48
第三章 纵横嵌入 51
§3．1 纵横扩张 51
§3．2 纵横凸嵌入 60
§3．3 注记 69
第四章 极大极小化 71
§4．0 基本约化 71
§4．1 3-可嵌入性 76
§4．2 2-可嵌入性 83
§4．3 1-可嵌入性 91
§4．4 注记 99
第五章 网格嵌入 100
§5．1 基本方程 100
§5．2 判别准则 103
§5．3 网格嵌入 114
§5．4 注记 122
第六章 最少孔道设计 124
§6．1 一般方法 124
§6．2 上界的估计 138
§6．3 注记 156
§7．1 最小面积扩张 157
第七章 最小面积设计 157
§7．2 渐近估计 164
§7．3 注记 176
第八章 定位与布线 178
§8．1 定位问题 178
§8．2 布线问题 191
§8．3 注记 203
第九章 分解术 205
§9．1 连通分解 205
§9．2 平面分解 211
§9．3 纵横分解 217
§9．4 注记 220
名词索引 223