# zbMATH — the first resource for mathematics

How to draw a planar graph on a grid. (English) Zbl 0728.05016
The authors show that every plane graph with n vertices has a straight- line embedding on the 2n-4 by n-2 grid, and provide an O(n) space, O(n.log n) time algorithm for finding the embedding. On the other hand, they prove that any set F, which can support a straight-line embedding of every planar graph of size n, has cardinality at least $$n+(1- o(1))\sqrt{n}$$. This settles a problem of B. Mohar.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory 05C35 Extremal problems in graph theory 68R10 Graph theory (including graph drawing) in computer science
##### Keywords:
planar grid; planar graph
Full Text:
##### References:
 [1] B.Chazelle, Slimming down search structures: a functional approach to algorithm design, inProceedings of the Twenty Sixth Annual Symposium on the Foundations of Computer Science,1985, 165–174. [2] N.Chiba, T.Yamanouchi and T.Nishizeki, Linear algorithms for convex drawings of planar graphs, inProgress in graph theory,1982, 153–173. [3] P. Duchet, Y. Hamidoune, M. Las Vergnas andH. Meyniel, Representing a planar graph by vertical lines joining different intervals,Discrete Math.,46 (1983), 319–321. · Zbl 0516.05023 [4] I. Fáry, On straight line representing of planar graphs,Acta. Sci. Math. (Szeged),11 (1948), 229–233. · Zbl 0030.17902 [5] H.de Fraysseix,Drawing planar and non-planar graphs from the half-edge code (to appear). [6] H.de Fraysseix and P.Rosenstiehl, Structures combinatoires pour traces automatiques do resaux, inProceedings of the Third European Conference on CAD/CAM and Computer Graphics,1984, 332–337. [7] H.de Fraysseix and P.Rosenstiehl,L’algorithme Gauche-droite pour le plongement des graphes dans le plan (to appear). [8] D. H.Greene,Efficient coding and drawing of planar graphs, Xerox Palo Alto Research Center. Palo Alto, CA. [9] P.Gritzmann and B.Mohar,private communication. [10] G.Grünbaum,Convex Polytopes, John Wiley. [11] J. Hopcroft andR. Tarjan, Efficient planarity testing,J. Comput. Mach.,21 (1974), 549–568. · Zbl 0307.68025 [12] F. T.Leighton,Complexity Issues in VLSI, The MIT Press. [13] B.Mohar,private communication. [14] R. H. J. M.Otten and J. G.van Wijk, Graph representation in interactive layout design, inProceedings of the IEEE International Symposium on Circuits and Systems,1978, 914–918. [15] P.Rosenstiehl, Embedding in the plane with orientation constraints,Ann. N. Y. Acad. Sci. (to appear). [16] R. C.Read, A new method for drawing a planar graph given the cyclic order of the edges at each vertex,Congressus Numerantium,56 31–44. [17] P. Rosenstiehl andR. E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs,Disc. Comp. Geom.,1 (1986), 343–353. · Zbl 0607.05027 [18] W. W.Schnyder,Planar Graphs and Poset Dimension (to appear). · Zbl 0675.06001 [19] R. Tommasia andI. G. Tollis, A unified approach to visibility representations of planar graphs,Disc. Comp. Geom.,1 (1986), 321–341. · Zbl 0607.05026 [20] W. T. Tutte, How to draw a graph,Proc. London Math. Soc,13 (1963), 743–768. · Zbl 0115.40805 [21] J. D.Ullman, Computational Aspects of VLSI,Computer Science Press. · Zbl 0539.68021 [22] L. G.Valiant, Universality considerations in VLSI circuits,IEEE Trans. on Computers,C-30, 135–140. · Zbl 0455.94046 [23] D. R. Woods,Drawing planar graphs, in Report N. STAN-CS-82-943, Computer Science Department, Stanford University, CA,1981.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.