Small sets supporting fary embeddings of planar graphs

ABSTRACT

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n - 4 by n - 2 grid and provide an &Ogr;(n) space, &Ogr;(n log n) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F, which can support a Fáry embedding of every planar graph of size n, has cardinality at least n + (1 - &ogr;(1)) √n which settles a problem of Mohar.

REFERENCES

• C: B. CHAZELLE Slimming down .~earch structures:a functional approach to algorithm design, in tUroceedin~Is of the Twenty Sixth Annua. l Symposium on the {~bundat/ons of C.,'omputer ,~'ci. ence. 1~)85, pp. 165-174.
• CYN: N. CmnA, T. YA~ANOUCnX, ,~Nt) T. N).~!ZZK1. Linear algorJthms for convex drawings of planar graph.in progress in ~raph theory, 1982, pp. 153-173.
• Dea: P. D,CitET, Y. HAMIDOUNE. M. LAs VER(;NAS, AND H. MEYNIEL. Representing a planar graph by vertical !iues joining ditferent intervals, Discrete Math., 46 (1983), {)Is. 319-321.
• F: l. FARY, On straight }i~e reprosenting of p~anar graphs, Acta.. qci. Math. (Szegetl), ii (1948}. pp. 229-233.
• dF: H. DE FHAYSSEIX, Drawing planar and non planar graphs from the half-e~!ge code, (to appear).
• dFR1: H. DE FHAYSSEIX, AND P. ROSENFIELD, .structure combinatoires !~,,ur tt~ces amtomagiql~e.do resaux,in proceedings of the ~J'hird gtaropean Conlgeren,'e on CAD CAM and computer Graphics, 1984, pp. 332-337.
• dFR2: H. DE FRAYSSEIX AND P. ROSENSTIEHL. L'alg,)rithme Gauchedroite pour le plongement des graphes dans le plan, (to appear).
• G: D. Fi. (3asEl~, efficient coding and drawing of planar graphs, Xerox PMo Alto Rese&rch Center. Palo Alto, CA.
• Gr: G. GI~/J~TBAUM, Convex Polytopes, John Wiley.
• HT: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• L: F.T. LmO~TON, Complexity Issues in VLSI, The MIT Press.
• M: B. MO~Aa, private communication.
• OvW: R.. H. J. M, OTTEN.~D J. G. v~,N WtJK. Graph representation in interactive layout design, in Proceedings of the IEEE International Symposium on Circuits and Systems, 1978, pp, ~14-918.
• R: P.ROSENSTIEHL, Embedding in the plane with orientation con- .~traints. Ann. N. Y. Acad. Sci. (to appear).
• Rd: R.C. RIs~,I), A new method for drafting a planar graph given the cyclic order o{ the edges at each vertex. Congres,s Numerantium, 56, pp. 31-44.
• RT: P. ROSENSTIEltL, A~D R. E. TAItJAN. Rectilinear,planarlayout.~ and bipolar orientations of planar graphs. Disc. Comp.Geom 1 (1986)' pp' 343--353'
• TT: R' TOM'MaSlA AND I. G. TOLLIS. A united approach to visit bilitr repre~entati,ms o{ planar graphs, Disc. Comp.Geom.,i (1986;, pp. 3'21-341.
• T: w.T. 'rrrvz. How to drawa graph. Pro~. Lt)mion Math. ,'qoc., 13 t 19631, pp. 743-768.
• U: Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
• V: L G. VALIANT. university considerations in VLSI circuits. iEEE Trans, on Computers ('-30. pp. 135-140.
• W: D.R. WOODS. Drawing planar graphs, in Report N. STAN-CS-- S2-943 , Computer Science Department, Stanford University, CA, 198I.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory