AT MOST SINGLE-BEND EMBEDDINGS OF CUBIC GRAPHS

作     者：刘彦佩 Marchioro,P. Petreschi,R. 

作者机构：Institute of Applied Mathematics Academia Sinica Beijing Department of Mathematics University of Rome “La Sapienza” Rome Italy 

出 版 物：《Applied Mathematics(A Journal of Chinese Universities)》 (高校应用数学学报（英文版）（B辑）)

年 卷 期：1994年第9卷第2期

页      面：127-142页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：05C10 57M50 94C15 Cubic graph sb-embedding st-numbering algorithm 

摘      要：This paper provides the complete proof of the fact that any planar cubic graph isat most slngle-bend embeddable except for the tetrabedrou. An O(n) amortized time algorithm for drawing an at most single-bend embedding of a cubic graph .is also presented, where n is the number of vertices of the graph. Furthermore, it is proved that the minimum of the total number of bends in an at most slngle-bend embedding of a cubic graph of order n is less than or equal to 0.5n+1. This result is the best possible.