On Planar Graphical Degree Sequences

SIAM J. APPL. MATH. Vol. 32, No. 3, May 1977. ON PLANAR GRAPHICAL DEGREE SEQUENCES* E. F. SCHMEICHEL" AND S. L. HAKIMIt Abstract. We determine completely which graphical sequences dl -> d2 ->" -->-- do with dl dp are planar graphical, and with a small number of exceptions determine the same result when dl-dp= 2. Y’ di) for a graphicalWe also give simple necessary conditions (in the form of upper bounds on i= sequence to be planar graphical. These conditions imply all known conditions of similar type, and often improve them. 1. Introduction. Throughout this paper, we consider only finite, undirected graphs without loops or multiple edges. Our terminology and notation will be standard, except as indicated. A nonincreasing sequence of positive integers 7r =(dl, d2," , do) is called graphical (planar graphical) if there exists a graph (planar graph) having 7r as its vertex degree sequence. Erd6s and Gallai [5] have shown that 7r is graphical if and only if "ff= di is even and =1 d ON PLANAR GRAPHICAL DEGREE SEQUENCES 599 condition for a graphical sequence r to be planar graphical is p+4 k 2p+6k-16 if3= 600 E.F. SCHMEICHEL AND S. L. HAKIMI and Po- 12 darkened vertices of degree 6. The two hatched polygons each consist of (1/2)(p-po) additional vertices of degree 6 arranged in each polygon in three horizontal rows of (1/6)(p-po) vertices each. The adjacency pattern of the vertices inside each polygon is assumed to be a continuation of the adjacency pattern indicated in Fig. 2. An alternative construction for the necessary realiza- tions has been given (in dual form) by Griinbaum and Motzkin [7]. The constructions to realize nonmaximal 1-sequences of the form 6r5s, p r + s >_- 16 will depend on the congruence class ofp modulo 6, and will be based on the graphs given in Fig. 2. p---O (mod 6) PO 18 p --- (mod 6) Po =19 p.=P_. p =:5 (mod 6) =14 po 15 FIG. 2 (cont.)D ow nl oa de d 11 /2 4/ 14 to 1 29 .1 20 .2 42 .6 1. R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur na ls /o js a. ph p ON PLANAR GRAPHICAL DEGREE SEQUENCES 601 p =-4 (mod 6) Po 16 p 5 (rood 6) FIG. 2 (cont.) If p ---0, 2, or 4 (mod 6), pair up the vertices of degree 6 in the corresponding mod p graph in Fig. 2, as indicated in Figs. 3, 4, and 5, respectively. (The darkened vertices in these latter figures correspond to the darkened vertices in Fig. 2, and the remaining vertices in these figures are the additionalp -Po vertices of degree 6 which constituted the hatched polygons in Fig. 2.) Removing these designated edges one by one will yield planar realizations of all nonmaximal 1-sequences of the form 6 5s. In particular, removing all these designated edges when p --- 2 or 4(mod 6), or all but one of them when p -= 0 (mod 6), will yield a planar realization of 625-2. If p 1, 3, or 5 (mod 6), pair up the vertices of degree 6 in the corresponding mod p graph in Fig. 2 as shown in Figs. 6, 7, and 8 respectively. (We require two distinct pairings when p 1 or 3 (mod 6), depending on the congruence class of p modulo 12). Removing these designated edges one by one will yield planar realizations of all nonmaximal 1-sequences of the form 6 5s. In particular remov- ing all of them would yield a planar realization of 615"-1. We can obtain planar realizations of 54 when p 14 or -> 16 from the realizations of 6z5"-z and 615p-1 described above. It is readily verified that whenp is even, the realization of 625’-z will contain a perfect matching, and that whenp is odd, the realization of 615-1 will contain a matching which omits exactly one vertex of degree 5. In either case, ifwe remove [(s + 2)/2] edges from the matching (including any edge incident to a vertex of degree 6) we will obtain a planar realization of 54.Downlo ad ed 1 1/ 24 /1 4 to 1 29 .1 20 .2 42 .6 1. R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur na ls /o js a. ph p 602 E.F. SCHMEICHEL AND S. L. HAKIMI p -= 2 (mod 6) FIG. 4 p= 4(rood6) FIG. 5 p -= (mod 12) ps 7 (mod 12) o----o c FG. 6 C 0 C 0 C 0 C 0 c o D ow nl oa de d 11 /2 4/ 14 to 1 29 .1 20 .2 42 .6 1. R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur na ls /o js a. ph p ON PLANAR GRAPHICAL DEGREE SEQUENCES 603 p =- 3 (mod 12:) C 0 C 0 @-----0 C 0 @ C, 0 (3 0 /0 C 0 C 0 / 0-----0 C -0 p =_ 9 (rood 12) o o . o o O 0 C 0 0 0 O 0 O 0 FIG. 7 p=_ 5 (mod6) FIG. 8 For p 13 or 15, we note that the argument of the preceding paragraph does not apply, since 61512 and 61514 (as well as 51241) are not planar graphical. We give planar realizations of 5143 and 544 in Fig. 9, however. It is then a simple matter to obtain realizations for the remaining 1-sequences of the form 5r4 whenp 13 or 15 by removing edges from the corresponding realizations in Fig. 9. Obtaining planar realizations of the remaining graphical 1-sequences d -d2 >_-" >-- dp when dl --< 4 orp 604 E. F. SCHMEICHEL AND S. L. HAKIMI and possibly the following unresolved cases: 7162513 7k615k+12 for k 2, 3, 5, 7, 7 5+12 for k 3, 5, 7, 9. Proof of Theorem 3. Since all maximal planar graphs (up to isomorphism) with nine or fewer vertices are given in [13, Appendix], we find immediately that 514431, 5333, 544132, 6146, 55423, 65245, and 574131 are not planar graphical. Moreover, 5931 and 75a3 are not planar graphical by Griinbaum’s theorem. A proof that 6x54 and 7x65 are not planar graphicalas well as the construc- tions necessary to obtain planar realizations of the remaining maximal 2- sequences (except for the unresolved sequences)are contained in a separate manuscript, which is available to anyone interested. A complete proof of Theorem 3 was previously given in [13]. TI-IEOREM 4. Every graphical, nonmaximal 2-sequence is planar graphical except for 4521, 51131, 6P-747 for p > 7 5533 71515 and possibly the following unresolved cases: 51331 71517 73517" Proof of Theorem 4. The result of Malkevitch mentioned in the proof of Theorem 2 immediately implies that none of the sequences 4521, 51131, and 71515 are planar graphical. If 5533 were planar graphical, a planar realization of it would contain exactly one four-sided face. Let v 1, v2, v3, v4 be the vertices incident to this face (in cyclic order). At least one of these vertices, say v l, would have degree 5. Consider the maximal planar graph G’ G + (vl, v3). If dego(v3) 3, then G’ is a maximal planar realization of 61544132 in which the vertices of degree 4 and 6 are adjacent. If dego(v3) 5, then G’ is a maximal planar realization of 625333. But neither type of graph exists (see [13, Appendix]), and thus 5533 is not planar graphical. Finally, if G were a planar realization of 6p-747 for some p > 7, and if v 1, vz, v3, v4 were the vertices incident to the four-sided face (in cyclic order), then G + (vl, v3) would be a G(2, 2) in which the two exceptional vertices are adjacent, FIG. 9 5104: 514’41 D ow nl oa de d 11 /2 4/ 14 to 1 29 .1 20 .2 42 .6 1. R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur na ls /o js a. ph p ON PLANAR GRAPHICAL DEGREE SEQUENCES 605 which does not exist by Griinbaum’s theorem. Hence 6’-747 is not planar graphical for any p > 7. The constructions needed to obtain planar realizations of the remaining nonmaximal 2-sequences (except for the unresolved sequences) are described in detail in the manuscript mentioned in the preceding proof. This completes the proof of Theorem 4. Q.E.D. 3. Necessary conditions tor a sequence to be planar graphical. We begin with the following result. THEOREM 5. Let dl >= d2 >-" >= do be a graphical sequence. Then: (a) If d3 3, a necessary condition for the sequence to be planar graphical is that p (3) Z d =- b -> 3. FIG. 10D ow nl oa de d 11 /2 4/ 14 to 1 29 .1 20 .2 42 .6 1. R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur na ls /o js a. ph p 606 E.F. SCHMEICHEL AND S. L. HAKIMI For part (b), observe that if d, >_-3, then (3) merely reduces to (1). Suppose therefore that (3) fails for some planar graph G with w(1) + o(2) > 0. In particular, this means p (4) Y, di >6[(p-w(1)-w(2))-2]+4to(2)+2w(1). i=1 Delete from G the w(1)+w(2) vertices of degree 1 or 2 to form a p-to(1)- o9(2)>3 vertex planar graph G; with vertex degree sequence d’l>=d&>= .>= d;-,o(a-,o(.. It follows from (4) that p--to(1)--to (2) 19 F, d’ >- F, di-4w(2)-2w(1)>6[(p-w(1)-w(2))-2], i=1 i=1 which contradicts (1). This proves (b). Q.E.D. As a corollary, we give our first necessary condition in the form of an upper kbound on the partial sums i=x d. COROLLARY 1. If dl >- d2 >-" >= do is planar graphical, then k p (5) Z d -< 6(k 2) + min (2, d)+ Y’, (4- i)Wk+l(i) i=1 i=k+l i3 ]’or k 3, 4,. ., p, where tOk+l(i) denotes the.number o]’times occurs as an element o" the sequence with index at least k + 1. Proof. From (3), we find that k p p p, di-- Y’, di- d- dE >=" >= dp to be planar graphical in the form of a bound on the partial sums. This bound will be a slight generalization of the bound (2) given by Bowen [2] and Chvfital [3]. THEOREM 6. If d >- dE >=" >= dp is planar graphical, then k 3k-4 p (6) F. di-- ON PLANAR GRAPHICAL DEGREE SEQUENCES 607 Proof. The proof when do -> 3 has been given by Bowen [2]. We will prove the case when do =< 2 by induction on p. It is trivially true if p 4, and so we assume the result for all planar graphs with Y di-min (2, dp) >6(k-2)+ Y min (3, d,)+ min (2, d) i=1 i=1 i=k+l i=3k-3 3k-4 p-1 ->6(k-2)+ E min(3, d’)+ Y. min(2, d), =k+l =3k-3 which contradicts the induction hypothesis. The assertion as to when the equality holds if dp _-< 2 can be proved similarly. Q.E.D. We combine the bounds in (5) and (6) to obtain a bound which is tighter than both (5) and (6) in the following corollary. (It should be noted that (5) is a tighter bound than (6) when k > (p + 4)/3.) COROLLARY 2. If d >= dz >=" >= d is planar graphical, then k 3k -4 (7) ] d_-3, 2= 3 The verification is tedious but straightforward. We conclude this development with a theorem which offers a still "better" condition than (7), in the sense that it becomes unnecessary to check (7) for all values of k when testing for planarity. On the other hand, the theorem reveals that (7) has limited value as a necessary condition for the planarity of a sequence, for it indicates that nearly every Euler sequence will satisfy (7). THEOREM 7. If dl >= d. >=.. >-_ d, is planar graphical then 3k-4 p k 6(k-2)+ Y. min(3, d)+ Y min(2, d) if3 608 E.F. SCHMEICHEL AND S. L. HAKIMI with equality homing under the same conditions as in Theorem 6. Proof. For 3-< k-< (p +4)/3, inequality (8) has been proved in Theorem 6. For k >(/9 +4)/3, the bound in (5) is tighter than the bound in (6) as we have noted. However, (5) is implied for all values of k by (3). Q.E.D. Eberhard [4], [6] has shown that any maximal Euler sequence can be made planar graphical if augmented with a sufficient number of 6’s. In this regard, Jucovi [10] and Barnette [1] established lower bounds for the number of 6’s required. Barnette’s bound holds even if the original sequence is nonmaximal, and can be expressed (after some routine manipulations) as follows: If d >=d >=. >- do is planar graphical, and _7 to(i)_-> 3, then w(6)=>8 Z w(i)+,1-- Z (i-8)w(i). i--= d2 >-" >-- do is planar graphical with a Yi>=7 to(i) >-_ 3, then 2 1 toa+l,3a-4(i),w(6)_->8-Zi_7 i=1,2 or 1 1E to(i)_->8- to(i)+ E (i-6)to(i)+to(1)+ toa+l,3a-4(i). i6 i5 i=>7 i 2 The desired inequality follows upon subtraction of a from both sides. Q.E.D. 4. Conclusions and applications. The complete characterization of planar graphical degrees sequences is an extremely difficult problem. The great variety of seemingly unrelated degree sequences which are not planar graphical (see Ttieorems 2-4 and observe, for example, that 6P-434 is planar graphical if and only if p ->_ 8 andp is even [7]) strongly suggests that the complete solution to the above problem is out of reach. Further results on planar graphical degree sequences may lead to better understanding of the structures of planar graphs and vice versa. Planar graphs arising in Whitney’s duality theory and coloring problems in graphs play major roles in many applications [14]. Also the study of the degree sequences of planar graphs may play some roles in the design of printed circuit boards and related layout problems, the design of reliable communication net- works, and geodesic design [15]. A more traditional application of the study of planar degree sequences [4], [8] has been its relation to the structures of polyhedraD ow nl oa de d 11 /2 4/ 14 to 1 29 .1 20 .2 42 .6 1. R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur na ls /o js a. ph p ON PLANAR GRAPHICAL DEGREE SEQUENCES 609 (see Steinitz’s theorem in [8]) which in turn has applications to linear and integer programming. REFERENCES [1] D. BARNETTE, On p-vectors of 3-polytopes, J. Combinatorial Theory, 7 (1969), pp. 99-103. [2] R. BOWEN, On the sums ofvalences in planargraphs, Canad. Math. Bull., 9 (1966), pp. 111-114. [3] V. CHVATAL, Planarity of graphs with given degrees of vertices, Nieuw Arch. Wisk., 17 (1969), pp. 47-619. [4] W. EBERHARD, Zur Morphologie der Polyeder, Teubner, Leipzig, 1891. [5] P. ERDtSS AND T. GALLAI, Graphs with prescribed degrees o[ vertices, Mat. Lapok., 11 (1960), pp. 264-274. [6] J. C. FISHER, An existence theorem for simple convex polyhedra, Discrete Math., 7 (1974), pp. 75-97. [7] B. GRONBAUM AND T. MOTZKIN, The number of hexagons and the simplicity of geodesics on certain polyhedra, Canad. J. Math., 15 (1963), pp. 744-751. [8] B. GRONBAUM, Convex Polytopes, Wiley-Interscience, New York, 1967. [9] A. HAWKINS, A. HILL, J. REEVE AND J. TYRELL, On certain polyhedra, Math. Gaz., 50 (1966), pp. 140-144. [10] E. JufovIC, On the number of hexagons in a map, J. Combinatorial Theory Ser. B, 10 (1971), pp. 232-236. [11] J. MALKEVITCI, Properties ofplanar graphs with uniform vertex andface structure, Mem. Amer. Math. Soc., 99 (1970). [12] A. B. OWENS, On the planarity of regular incidence sequences, J. Combinatorial Theory Ser. B, 11 (1971), pp. 201-212. [13] E. SCHMEICHEL, The cycle structure and planarity of graphs under degree constraints, Ph.D. thesis, Northwestern Univ., Evanston, Ill., 1974. [14] N. DEO, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, N.J., 1974. [15] P. BARAN, On Distributed Communication Networks, IEEE Trans. Comm. Systems, CS-12 (1964), pp. 1-9. D ow nl oa de d 11 /2 4/ 14 to 1 29 .1 20 .2 42 .6 1. R ed is tr ib ut io n su bj ec t t o SI A M li ce ns e or c op yr ig ht ; s ee h ttp :// w w w .s ia m .o rg /jo ur na ls /o js a. ph p