最优画法的一个充分条件

A sufficient condition of optimal drawing

设D是图G的一个好画法,将G在画法D下的交叉点看成新的顶点,这样得到的图称为G在画法D下的导出平图,记为G_D。即G_D的顶点集V(G_D)=V(G)∪{交叉点},边e由D\V(G_D)的片段组成,并且顶点v和边e关联的充分必要条件是v在边e的闭包里。本文证明了:如果画法D的导出平图的每个面的度数都是3,则D是最优画法。

Let D be a good drawing of the graph G, the induced plane graph of D, denoted by Go, is the graph with vertices V（GD）= V（G） ∪{ crossings} , where the edges are the components of D ／ V（ GD） and v is incident to e if and only if v is in the closure of e. In this paper, we prove that if each face of the induced plane graph GD of D is triangle, then D is optimal.