Algorithmic advances via graph decomposition

Abstract

Many fundamental and natural problems considered in computer science are known to be NP- hard. This is widely believed to make the existence of efficient algorithms, i.e. algorithms that scale well with respect to the size of their input, unlikely. However the situation may of course change if one imposes structural restrictions on the input. A refined analysis taking this into account is useful – both from the natural theoretical standpoint of asking for a detailed complexity classification, as well as from the practical standpoint of wanting to exploit the structure inherent to real-life instances and applications. The form interesting structural restrictions can take is as diverse as these problems and their instances. Our focus lies on decompositional parameters, the most prominent of which is treewidth. Our results fall within both the study of decompositional parameters, as well as their application.We define and investigate two general decompositional parameter schemes, with different underlying motivations. Firstly, we augment treewidth by conceptually allowing large subgraphs that are forbidden by bounded treewidth, so long as they are in some graph class H. This gives rise to H-treewidth for arbitrary H and allows us to combine treewidth and other helpful graph properties. Secondly, we identify a set of parameters that provide a surprisingly concise shared perspective on, and formalisation of, the most important known decompositional parameters. Algorithmically, we show how this allows us to formulate unified algortihms to approximate the captured parameters.Complementing this fundamental research into decompositional parameters, we present a set of concrete algorithms for near-planar extension of partial graph drawings.