Drawing Plane Graphs via Graph Orientations

Graph representations play an important role in graph theory. A good and clear graph representation helps us capture graph information easily. In this thesis, we discuss three well-known graph representations, namely, rectangular layout, visibility representation and greedy drawing. The formal definitions for the three representations will be given later.;The rectangular layout is an interesting and important representation of plane graphs. A rectangular layout L is a rectangle partitioned into a number of interior disjoint smaller rectangles. They are used as rectangular cartograms in cartography, as floorplans in VLSI design, and in graph drawing applications. In these applications, areas are often assigned to the rectangles in a rectangular layout. It is desirable for one rectangular layout L to represent several area assignments. A rectangular layout L is called area-universal if any assignment of areas to rectangles can be realized by a layout that is combinatorially equivalent to L. A basic problem in this area is to determine if a given plane graph G has an area-universal rectangular layout or not. A fixed-parameter-tractable algorithm for solving this problem was obtained recently [13]. Their algorithm takes O(2O(K2)nO(1)) time, where K is the maximum number of degree 4 vertices in any minimal separation components. For a fixed K, the algorithm runs in polynomial time. However, their algorithm takes exponential time in general case. It is an open problem to find a true polynomial time algorithm for solving this problem.;In this thesis, we describe such a polynomial time algorithm. Our algorithm is based on new studies of properties of area-universal layouts. The polynomial run time is achieved by exploring their connections to the regular edge labeling construction.;The visibility representation (VR for short) is a classical representation of plane graphs. It has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. The trivial upper bound is (n-1) x (2n-5) (height x width). It is known that there exists a plane graph G with n vertices where any VR of G requires a grid of size at least 2/3n x (4/3 n-3). For upper bounds, it is known that every plane graph has a VR with grid size at most 2/3n x (2n -5), and a VR with grid size at most (n-1) x 4/3n. It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely with size at most chn x cwn with ch < 1 and cw < 2).;We have obtained the first VR construction with this property. We prove that every plane graph of G vertices has a VR with height at most 23/24n+2[√n]+10 and width at most 23/12n. The area of our VR is larger than the area of some of the previous results. However, bounding one dimension of the VR only requires finding a good st-orientation or a good dual s*t*-orientation of G. On the other hand, to bound both dimensions of VR simultaneously, one must find a good st-orientation and a good dual s*t*-orientation at the same time, which is far more challenging. Our VR algorithm is based on an st -orientation of plane graphs with special properties. Since st-orientations are a very useful concept in other applications, this result may be of independent interests.;Finally, geometric routing by using virtual locations is an elegant way for solving network routing problems. Greedy routing, where a message is simply forwarded to a neighbor that is closer to the destination, is a simple form of geometric routing. A greedy drawing of a graph G is a drawing of G for which the greedy routing works.;In this thesis, we show that every 3-connected plane graph has a drawing on the R2 plane that is succinct, planar, strictly convex, and is greedy with respect to a metric function.