Graph orientation, labeling and their applications

Abstract

Graphs are widely used to represent information that can be modeled as objects and connections between those objects. A graph orientation assigns a direction to each edge of the graph. A graph labeling assigns distinct numbers from 1 to n to all the vertices of the graph. Graph orientations and graph labelings are two important techniques used in graph theory, graph algorithm and graph drawing. We investigate some applications of them in this research. Recently, Hoffmann and Kriegel proved an important combinatorial theorem: Every 2-connected bipartite plane G has a triangulation in which all vertices have even degree (it's called an even triangulation). A complicated O ( n 2 ) time algorithm was obtained by them for constructing an even triangulation of G. They conjectured that there is an O ( n 3/2 ) time algorithm for solving this problem. Using this theorem, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. This proof was purely algebraic and it cannot be extended to similar graphs embedded on high genus surfaces. It's not known whether Hoffmann and Kriegel's Theorem is true for such graphs. We develop a totally independent and much simpler proof of the above theorem, using graph orientation technique. Our new proof can be easily extended to show the existence of even triangulations for similar graphs on high genus surfaces. Our proof also leads to a very simple linear time algorithm for finding even triangulations. The visualization of complex conceptual structures is a key component of support tools for many applications in science and engineering. Many information visualization systems require graphs to be drawn so that they are easy to read and understand. There are many styles of graph drawing. A visibility representation (VR) of a plane graph G is a representation, where the vertices of G are represented by non-overlapping horizontal vertex segments, and each edge of G is represented by a vertical line segment touching the vertex segments of its end vertices. The problem of computing a compact VR is important not only in algorithmic graph theory, but also in practical applications such as VLSI layout. We use the graph labeling technique to obtain more compact VR of plane graphs. We also present several open problems for future research.