Intersection graphs and geometric objects in the plane
Udo Hoffmann · DepositOnce · 2016
In this thesis, we consider several aspects of representations of graphs in the plane. We consider mainly intersection and visibility representations of graphs. In both kind of representations, the vertices are represented by sets in the plane. Intersection representations represent the edges by the intersection of two sets. In visibility graphs, an edge corresponds to a visibility between the sets. In the first part, we consider connections between representations of bipartite segment intersection graphs and their order dimension. In Chapter 1, we show that the order dimension of grid intersection graphs, the intersection graphs of horizontal and vertical segments, is at most four. We use this observation to study the containment relation of many subclasses of grid intersection graphs. We generalize the observation on the order dimension of grid intersection graphs, by showing that the order dimension of bipartite segment intersection graphs is at most linear in the number of slopes that is used in a representation. This leads to the study of the slope number of segment intersection graphs, the minimal number of slopes that is sufficient to represent an intersection graph. In Chapter 2, we show that the slope number of segment intersection graphs is NP-hard to compute, and that it behaves "non-continuously'', i.e., it may drop, from a linear number in the number of segments down to two, upon the removal of a single vertex. The proofs in the first part are based on combinatorial properties of the graphs. In the second part, we deal with the realizability problem and the complexity class existential theory of the reals (ETR). Many geometric representation problems for graphs are complete in ETR, for example the recognition of segment intersection graphs. We show that computing the slope number of segment intersection graphs (Chapter 4) and the recognition of point visibility graphs (Chapter 5) is complete in ETR. Both proofs are based on the ETR-hardness of the realizability of circular sequences, the order of slopes of lines that are spanned by a point sets, which we present in Chapter 3. We finish in Chapter 6, by showing that determining the minimum number of slopes that is sufficient for a planar straight line drawing of a graph, the planar slope number of a graph, is also complete in ETR. We discuss consequences the ETR-hardness for properties of the representation.