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.
@article{10_37236_2378,
author = {Keith Edwards and Graham Farr},
title = {Improved upper bounds for planarization and series-parallelization of degree-bounded graphs},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2378},
zbl = {1243.05066},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2378/}
}
TY - JOUR
AU - Keith Edwards
AU - Graham Farr
TI - Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2378/
DO - 10.37236/2378
ID - 10_37236_2378
ER -
%0 Journal Article
%A Keith Edwards
%A Graham Farr
%T Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2378/
%R 10.37236/2378
%F 10_37236_2378
Keith Edwards; Graham Farr. Improved upper bounds for planarization and series-parallelization of degree-bounded graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2378
