Minimum-Width Grid Drawings of Plane Graphs (Extended Abstract)

Chrobak, Marek and Nakano, Shin-Ichi (1995) Minimum-Width Grid Drawings of Plane Graphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 104-110 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_361).

Full text not available from this repository.

Abstract

Given a plane graph G, we wish to draw it in the plane, according to the given embedding, in such a way that the vertices of G are drawn as grid points, and the edges are drawn as straight-line segments between their endpoints. An additional objective is to minimize the size of the resulting grid.It is known that each plane graph can be drawn in such a way in a (n - 2) \times (n - 2) grid (for n \geq 3), and that no grid smaller than (2n/3 - 1) \times (2n/3 - 1) can be used for this purpose, if n is a multiple of 3. In fact, it can be shown that, for all n \geq 3,each dimension of the resulting grid needs to be at least [2(n - 1)/3], even if the other one is allowed to be infinite. In this paper we show that this bound is tight, by presenting a grid drawing algorithm that produces drawings of width [2(n - 1)/3]. The height of the produced drawings is bounded by 4[2(n - 1)/3] - 1.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_361
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
P Styles > P.999 Others
P Styles > P.540 Planar
ID Code:103

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis, Automatic graph drawing: an annotated bibliography, to appear in Computational Geometry: Theory and Applications.

M. Chrobak, T. Payne, A linear-time algorithm for drawing planar graphs on a grid, Technical Report UCR-CS-89-1, Department of Mathematics and Computer Science, University of California at Riverside, 1989.

M. Chrobak, G. Kant, Convex drid drawings of 3-connected planar graphs, Technical Report RUU-CS-93-45, Department of Computer Science, Utrecht University, 1993.

I. Fáry, On straight lines representation of plane graphs, Acta. Sci. Math. Szeged 11 (1948) 229-233.

H. de Fraysseix, J. Pach, R. Pollack, Small sets supporting Straight-Line Embeddings of planar graphs, Proc. 20th Annual Symposium on Theory of Computing, 1988, pp. 426-433.

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

G. Kant, Drawing planar graphs using the lmc-ordering, Proc. 33rd Symp. on Foundations of Computer Science, Pittsburgh, 1992, pp. 101-110.

G. Kant, Algorithms for Drawing Planar Graphs, Ph.D. Dissertation, Department of Computer Science, University of Utrecht, 1993.

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

S. K. Stein, Convex maps, Proc. Amer. Math. Soc., 2 (1951) 464-466.

K. Wagner, Bemerkungen zum vierfarbenproblem, Jahresbericht der Deutschen Mathematiker-Vereinigung, 46 (1936) 26-32.