@phdthesis{Beisegel2020, author = {Beisegel, Jesse}, title = {Convexity in graphs: vertex order characterisations and graph searching}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-51452}, school = {BTU Cottbus - Senftenberg}, year = {2020}, abstract = {We study convexities designed to characterise some of the most fundamental classes of graphs. To this end, we present some known results on this topic in a slightly different form, so as to give a homogeneous representation of a very disparate field. Furthermore, we present some new results on the Caratheodory number of interval graphs and also give a more or less exhaustive account of everything that is known in this context on AT-free graphs, including new results on characterising linear vertex orders and the structure of the intervals of this class. We introduce the new class of bilateral AT-free graphs which is motivated by the linear order characterisation and the convexity used to describe AT-free graphs. We discuss their relation to other known classes and consider the complexity of recognition. Furthermore, as a consequence of notions from abstract convexity we present algorithmic results with regards to some natural subclasses of these. As an application of notion of an extreme vertex of a convex geometry, we discuss structural aspects of avoidable vertices in graphs, which form a generalisation of simplicial vertices. This includes a characterisation of avoidable vertices as simplicial vertices in some minimal triangulation of the graph and a new proof of the existence result. Furthermore, we discuss the algorithmic issues regarding the problem of efficient computation of avoidable vertices in a given graph. This is complemented by an algorithmic application of the concept of avoidable vertices to the maximum weight clique problem, by identifying a rather general class of graphs in which every avoidable vertex is bisimplicial. This leads to a polynomial-time algorithm for the maximum weight clique problem in this class of graphs. Implications of this approach for digraphs are also discussed. All of these results lead to a conjecture concerning the generalisation of avoidable vertices to avoidable paths and we prove this conjecture for paths of length less or equal to two. Finally, we analyse the properties of many different and widely used forms of graph search. Here, we discuss the problem of recognising whether a given vertex can be the last vertex visited by some fixed graph search. Moreover, we present some new aspects of the problem of deciding whether a given spanning tree of a graph is a graph search tree of a particular type of search. We generalise the concept of such trees to many well-known searches and give a broad analysis of the computational complexity of this problem. Both of these discussions are motivated by the use of graph searches in the context of computing properties of convexity.}, subject = {Graph convexity; Convex geometry; Graph searching; Vertex order characterisation; Asteroidal triples; Asteroidale Tripel; Lineare Knotenordnung; Graphensuche; Konvexe Geometrie; Konvexit{\"a}t; Graph; Konvexit{\"a}t; Konvexe Geometrie}, language = {en} }