TABLE OF CONTENTS Kao et al. [KFHR94] efficiently parallelized the construction of realizers of triangulated planar graphs and gave an optimal parallel algorithm for straight line grid drawings of planar graphs. Di Battista et al. [DTV99] extended the definition of realizers to 3-connected planar graphs and gave efficient output-sensitive algorithms for performing k-path queries, and also gave an algorithm for finding convex grid drawings of 3-connected planar graphs. Miura et al. [MTNN99] extended the definition of realizers to four-connected plane graphs and used it to solve the independent spanning tree problem. Generalizing a canonical ordering and a realizer, Chiang et al. introduced the concept of an orderly spanning tree for maximal planar graphs, which has many applications in graph encoding and graph drawing [CLL01]. Miura et al. showed that a Schnyder labeling, a realizer, a canonical decomposition, an orderly spanning tree and an outer triangular convex grid drawing are notions equivalent with each other for plane graphs such that each vertex has degree three or more [MAN04].
Write a program to implement the algorithm of de Fraysseix et al. so that it takes time O( n 2).
Using the shift method, design an algorithm to find a straight line grid drawing of a plane graph of n vertices on an ( n ?1) ( n ?1) grid.
Design and implement a linear algorithm to construct a Schnyder labeling of a triangulated plane graph.
Let G be...
