# Problems in Geometric Graph Theory

*by Michael Payne*

*Institution:*Dept of Mathematics & Statistics, The University of Melbourne

*Date: Tue 25th January 2011*

*Time: 3:00 PM*

*Location: Room 215, Richard Berry Building, The University of Melbourne*

*Abstract*: Geometric Graph Theory deals with classes of graphs that arise from various geometric settings. During my first year of candidature I have

addressed problems involving two such classes. The first is that of colouring great circle arrangement graphs. These graphs have the

crossing points of a set of great circles as vertices and the arcs as edges. Since they are planar graphs they are 4-colourable, but it is

conjectured that three colours suffice. The second problem involves the visibility graphs of point sets in the plane. Two points in the set are joined by an edge if no other point lies on the straight line

segment between them. I have investigated the question of whether visibility graphs with a fixed clique number (c) have bounded chromatic number. The answer is known to be yes for c=3 and no for

c=6. I have studied the first remaining case, c=4.

*For More Information:* contact: David Wood. email: woodd@unimelb.edu.au