Extension Properties of Graphs and Structures
Pavel Klavík · Digital Repository (National Repository of Grey Literature) · 2017
Extension Properties of Graphs and Structures Pavel Klavík The main motivation for graph drawing and geometric representations is finding ways to visualize graphs efficiently to make their structure as understandable as possible. In this thesis, we are concerned with structural properties which are implied for graphs having certain geometric representations. We study two types of geometric representations: inter- section representations in which the vertices are represented by geometric sets while the edges are encoded by their intersections, and planar embeddings of planar graphs which are drawing of graphs into the plane without crossing edges. The existence of geometric representations can be used to deduce additional information about graphs. The main idea of this thesis is to ask what extra information can be deduced from the structure of all possible geometric representations. In Part I, we study the partial representation extension problems for intersection rep- resentations. Aside from the graph, the input also gives a partial representation, which prescribes a representation of an induced subgraph. We ask whether this partial repre- sentation can be extended to a full representation of the input graph without altering the predrawn sets. I introduced this problem in 2010 in my Bachelor's thesis. We...