关于单位区间图的二维带宽问题  

Two-dimensional bandwidth problem for unit-interval graph

作　　者：吕红杰[1] 申家峰[2] 戴明清[3] 

机构地区：[1]郑州轻工业学院信息与计算科学系,河南郑州450002 [2]郑州航空工业管理学院基础部,河南郑州450015 [3]华北水利水电学院数学系,河南郑州450011

出　　处：《郑州轻工业学院学报（自然科学版）》2006年第1期96-99,共4页Journal of Zhengzhou University of Light Industry:Natural Science

摘　　要：二维带宽问题是将图G的顶点嵌入平面格子图,使其最长的连线尽可能短.通过引进矩形链这一概念,给出单位区间图的二维带宽精确值.The two-dimensional bandwidth problem is to find an embedding of graph G in a grid graph in the plane so that the longest edges are as short as possible. The exact value of two-dimensional bandwidth for unitinterval graph is produced.

关 键 词：二维带宽 单位区间图 图的嵌入 

分 类 号：O157.5[理学—数学]