Grid Embedding of 4-Connected Plane Graphs

He, Xin (1996) Grid Embedding of 4-Connected Plane Graphs. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 287-299 (Official URL: http://dx.doi.org/10.1007/BFb0021812).

Full text not available from this repository.

Abstract

A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as non-intersecting straight line segments. In this paper, we show that, if a 4-connected plane graph G has at least 4 vertices on its exterior face, then G can be embedded on a grid of size W \times H such that W + H \le n, W \le (n + 3)/2 and H \le 2(n - 1)/3, where n is the number of vertices of G. Such an embedding can be computed in linear time.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021812
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others
ID Code:157

Repository Staff Only: item control page

References

N. Chiba, T. Yamanouchi, and T. Nishizeki, Linear algorithms for convex drawings of planar graphs, in Progress in Graph Theory, J. A. Bondy and U. S. R. Murty (eds.), 1982, pp. 153-173.

M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar graphs, Tech. Rep. RUU-CS-93-45, Dept. of Comp. Sci. Utrecht University, 1993.

M. Chrobak ans S. Nakano, Minimum-width grid drawings of planar graphs, in Proc. Workshop on Graph Drawing '94, Princeton, NJ, Oct. 1994.

M. Chrobak and T. Payne, A linear time algorithm for drawing planar graphs on a grid, TR UCR-CS-89-1, Dept. of Math. and Comp. Sci., UC at Riverside, 1989.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Comput. Geom. Theory Appl. Vol 4, 1994, pp. 235-282.

I. Fáry, On straight line representation of planar graphs, Acta. Sci. Math. Szeged, 11, 1948, pp. 229-233.

H. de Fraysseix, J. Pach and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10, 1990, pp. 41-51.

M. Fürer, H. He, M. Y. Kao, and B. Raghavachari, O(n log log n)-work parallel algorithms for straight line grid embeddings of planar graphs, SIAM J. Disc. Math 7(4), 1994, pp. 632-647.

G. Kant, Drawing planar graphs using the lmc-ordering, in Proc. 33th Ann. IEEE Symp. on Found. of Comp. Science, Pittsburgh, 1992, pp. 101-110.

G. Kant and X. He, Two algorithms for finding rectangular duals of planar graphs, in Proc. 19th on Graph-Theoretic Concepts in CS, 1993, LNCS 790, pp. 396-410.

F. Preparata and R. Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures, in Proc. 29th FOCS, 1988, pp. 558-567.

P. Rosenstiehl and R. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete & Computational Geometry 1, 1986, pp. 343-353

W. Schnyder, Embedding planar graphs on the grid, Abs. AMS 9, 1988, p. 268.

W. Schnyder, Planar graphs and poset dimension, Orders 5, 1989, pp. 323-343.

W. Schnyder, Embedding planar graphs on the grid, in Proc. of the 1st Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 138-147.

W. Schneider and W. Trotter, Convex drawings of planar graphs, Abstracts of AMS 13 (5), 1992.

S. K. Stein, Convex maps, in Proc Amer Math Soc, Vol. 2, 1951, pp. 464-466.

W. T. Tutte, How to draw a graph, Proc. London Math. Soc. 13, 1963, pp. 743-768.

K. Wagner, Bemerkungen zum Vierfarbenproblem, Jahresbericht Deutsch Math 46, 1936, pp. 26-32.