Models of Graph Classes and Applications

Abstract

This dissertation studies models of graph classes. We explore how models can be used to define new graph classes that either generalize or combine multiple properties. Further, we examine when and how such properties can help us design efficient algorithms for recognition and optimization problems on the class. We also consider how properties of graph class models can affect the dynamics of processes taking place over a graph. We first introduce a novel model that generalizes the geometric intersection models of interval and permutation graphs. As a result, we obtain a new class of graphs - interval-permutation segment (IP-SEG) graphs - that generalizes interval and permutation graphs but is not contained within the class of perfect graphs. Using properties of the geometric intersection model, we design polynomial model-based algorithms for optimization problems on IP-SEG graphs. We also present a polynomial algorithm for recognizing IP-SEG trees. Secondly, we consider vertex orderings as a model for characterizing or representing special classes of graphs. We give the first robust polynomial algorithm for finding the maximum clique in IP-SEG graphs that is based on a vertex elimination ordering. Further, we consider two different methods of combining vertex ordering properties and show examples where this leads to a class of graphs on which a generally hard optimization problem becomes tractable. Lastly, we study how properties of different class models can affect the process of decentralized consensus between agents positioned as vertices of a graph. We consider multiple graph classes and associated random generating models and we analyze how structural properties of the underlying graph can impact the effectiveness of mechanisms for facilitating or preventing decentralized consensus.