Improved upper bounds for planarization and series-parallelization of degree-bounded graphs

被引:0
作者
Edwards, Keith [1 ]
Farr, Graham [2 ]
机构
[1] Univ Dundee, Sch Comp, Dundee DD1 4HN, Scotland
[2] Monash Univ, Clayton Sch Informat Technol, Clayton, Vic 3800, Australia
关键词
fragmentability; planarization; series-parallel; tree width; regular expression; FRAGMENTABILITY;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We study the number of vertices which must be removed from a graph in order to make it planar or series-parallel. We give improved upper bounds on the number of vertices required to planarize graphs of bounded average degree d, and for small d also an improved bound for series-parallelization. The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. The above bounds on planarization yield improved bounds for the coefficient of fragmentability of the class of connected graphs of average degree at most d. As an application we give an improved bound on the size of regular expressions representing deterministic finite automata.
引用
收藏
页数:19
相关论文
共 10 条
[1]  
de Fraysseix H, 2002, LECT NOTES COMPUT SC, V2265, P84
[2]  
Edwards K, 2002, LECT NOTES COMPUT SC, V2265, P75
[3]   NEW UPPER-BOUNDS ON HARMONIOUS COLORINGS [J].
EDWARDS, K ;
MCDIARMID, C .
JOURNAL OF GRAPH THEORY, 1994, 18 (03) :257-267
[4]   Fragmentability of graphs [J].
Edwards, K ;
Farr, G .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 82 (01) :30-37
[5]  
Edwards K. J., TOPICS STRU IN PRESS
[6]   Planarization and fragmentability of some classes of graphs [J].
Edwards, Keith ;
Farr, Graham .
DISCRETE MATHEMATICS, 2008, 308 (12) :2396-2406
[7]  
Gruber H, 2008, LECT NOTES COMPUT SC, V5257, P383, DOI 10.1007/978-3-540-85780-8_30
[8]  
Halldorsson M. M., 1997, Journal of Graph Algorithms and Applications, V1
[9]   Maximum acyclic and fragmented sets in regular graphs [J].
Haxell, Penny ;
Pikhurko, Oleg ;
Thomason, Andrew .
JOURNAL OF GRAPH THEORY, 2008, 57 (02) :149-156
[10]  
Liebers A., 2001, Journal of Graph Algorithms and Applications, V5