Some Problems Of Geometric Graph Theory

Geometric graph theory focuses on the graph structures introduced by the ge-ometric relationship, as well as geometric representations for graphs and the related problems. This thesis concentrates on competition graphs and double competition graphs, especailly on the double competition graphs of the plane, and the crossing number of simultaneous embedding of two planar graphs.The first part studies questions arising from competition between species. Let D= (V(D),A(D)) be a digraph. The competition graph of D, is the graph with vertex set V(D) and edge set(?). The double competition graph of D, is the graph with vertex set V(D) and edge set (?). Competition graphs were introduced by Cohen to study ecosystem. Since then, severval variations in-cluding double competition graphs have been defined and studied by many authors. Besides the application to ecology, competition graphs have also found application in coding, studying communication over noisy channels, interfering radio transmis-sions, and models of complex economic and energy problems. As a poset is an acyclic transitive digraph, the competition graph and double competition graph of a poset can be similarly defined. A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R2 and there is an arc go-ing from a vertex (x1,y1) to a vertex (x2,y2) if and only if x1> x2 and y1> y2. The (double) competition graph of this poset is briefly called the (double) compe-tition graph of the plane. The competition graph and double competition graph of a digraph and a poset, especially of the plane, will be studied in the first four chapters.Chapter 1 is a very brief survey of competition graph.Chapter 2 starts with the summarization of the known results on the charac-terization of competition graphs and competition numbers. Then the competition graph of a poset is characterized. Some connections are also established in this chapter between the minimum numbers of isolated vertices required to be added to make a given graph into the competition graph, respectively, double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph.Chapter 3 deals with the competition graph of the plane. We show that a graph is the competition graph of the plane if and only if it is an interval graph at least half of whose maximal cliques are isolated vertices. This answers an open question on doubly partial order competition number posed by Cho and Kim.Chapter 4 is about the double competition graph of the plane. Let (?) denote the set of this double competition graph. We first prove (?) is a proper subclass of trapezoid graphs, generalizing the main results of Kim, Kim and Rho. Moreover, we show some necessary conditions for a graph to lie in (?). Then we list two minimal forbidden subgraphs for (?), and finally report the relationship between the class (?) and some well-studied graph classes such as the subclasses of trapezoid graphs and various subclasses of tolerance graphs.The second part studies the crossing number of simultaneous embedding of two planar graphs. The graph G is a planar graph if it can be embedded on the plane such that any two edgs of G have no crossing other than their common endpoint. Consider a red planar graph and a green planar graph simutaneously embedded on the plane. With some restriction, a red edge can cross a green edge, this red/green edge-crossing is called a crossing. The crossing number is the minimum number of crossings among all the simultaneous embeddings of two planar graphs with restriction. We make some observations on this crossing number in chapter 5.