Discovery - University of Dundee - Online Publications

Library & Learning Centre

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

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

Research output: Contribution to journalArticle

View graph of relations

Authors

Research units

Info

Original languageEnglish
Article numberP25
Number of pages19
JournalElectronic Journal of Combinatorics
Journal publication date31 May 2012
Volume19
Issue2
StatePublished

Abstract

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 coeffcient 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 coeffcient 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.

Documents

Library & Learning Centre

Contact | Accessibility | Policy