Orienting planar graphs

Orienting planar graphs

Received 12 M,lrch 1975 Rcviscd 3 June 1935 It is &own that every rnzknal plsnar graph Itriangulakn) can be contracted at an arbitrary point (by iden...

580KB Sizes 0 Downloads 41 Views

Received 12 M,lrch 1975 Rcviscd 3 June 1935

It is &own that every rnzknal plsnar graph Itriangulakn) can be contracted at an arbitrary point (by identifying it with an adjacent point) c,o that triangularity is preserved. This is used as B lemma to prove that every triangulation con be (a) oriented so that with threg: exceptions every point hs indcgree three, the exceptions having indegrees 0,l and 2, and (15)decomposed into three edge-disjoint trees of equal order. The lemma also provides MI elementary proof of a theorem of Wagner that cvdty triangulatiljn can be re!presentcd bly a straight-line drawing.

his note presents a proof that any planar graph can be oriented so that no point has more than three entering lines. If such a directed graph has no dir&e4 cycles, it is four-colorable, since it can then be colored @;r a~~pl~cat~~nof the rule “color point 11differently frw-n the initia all thiat a graph is oriented by replacing its lines Gth directed lines,


Fig. 1. Three Tlgraphsand ii muitqyaph.

planar graph, it will suffice ta prove the theu~m

fur all TI

ph diivides the plane Ento regions bounded by elernentur~ cycles of length three whose interiors or extltrisrs are empty. es are T_adiatwrt if they belong to the same elem\entary ;riangle. If pq is a iine beiongintg 710two drstincti ekmcntary triangles ipuq and puq, we a T-contrmtion along pq ,as the transformaiiorr carried out by (a) the lint;e pq, uq and uq from the graph, (b) replacing thepremaines incident with q by lines inciden’ with p, and (c) removing q. ff suit is a T-graph, pq iz;said to ‘be T-contractable. or example, gq in Fig. ‘1 is Rontractable since the result of a T-contra~ti~~ a.iong pq is the “T-graph T4 L Lines of the triangle uqu a:~ neither T-adjacent nor T-contractable since rqu is nut elementary and a contracIti one of ltts lines yields a graph isomorphic to M4 . a statinjrr that every T-graph contains a T-contractable edge ’ the literature in variant forms; in particular, a dual version is tein 141. A stronger version can be stated as f&xv-s:

T4 ) the unique T-graph of order 4. s of order less than H fbr some ~1> 4, s not T-contractablc:


Fig. 2. Sitwtion when pq is not T-emtractable.

Moreover, since the 7’0contractiora along pq does s,at yield- a T-graph, it must create a multiplicity, and this c3n only happen if pq rird distinct triangle pwq. We may aw.me without loss of generality that point M ies in the interior of pwq. Then point u lies in the exterior (see Fig. 2), and if we delete all the points and lines exterior to ywq the result is a T-graph Tk of’ order less th,irl n. By the induction hypothesis, the lemma holds for Tk. Since paazand pq are T-adjacent in 7”) there is at least one T-contractable line py interior topwq, and this line is 7’-contractable in Tn as well. By a symmeWc argument, 17is incident with a :I”-contractable line px exterior to pwq. Since PX and py are separated by pwq and therefore cannot be ?kdjacent, p is incident with at least two non-T-adjaczni. T~zontractable lines. The lemma holds by induction. ‘Ifwe agree to call the inverse of a T-contraction a T-expansion, the lemma provides a characterization of planar grap s as subgraphs of graphs generated from T3 by a sequence af T-expansions.

. The theorem clearly holds for lq3. Assume that it holds for all1Tgraphs sf order f -ss tb than n for surne n > 3, an let prs be an elementa triangle of a T-gra h T, of order tt. y the lemma, Tll contains a T-contractable line 1~)

so, WCreversje the
e temma c;rn be used in similar fashion to prove $;uch properties of 4r reiating the number of lines e, a$e=y--2r. Htalso pmvides an efementary proof of the fufsuft of Wag=ner[ 5 1, Easy I 1] v a:nd Stein [43.

The theorem clearly holds kz T3. Assume that it holds fur ali hs of order less than r~ for some I! > 3, and let lPti be an arbitrary contains a T-contractable line pq. Let puq and puq djacent elementary triangles. Contracting T, :tIrrngpq, we ob1. By the induction hyp esis, we can draw g straight-iinc segments. e Zhen reverse the its incident line segments ijway from p along ucp~,and adding straight-line segments pq, ur;t f the sepzxation of p and 4 ?s small enough, (b) will be mtisfied e resulting Frtane graph. (A similar argument is used in [3, pp. 7-81 .I y TN, and by induction for all n.

operty: If x, y and


Assume that it holds for all T-graphs of order less than r1 for some 0 > 3, and let s, y a~~ z tx distinct points of a T-graph TF,. Since n ‘> 3, there is a point 4 distinct from x, J* and .z, and by the lemma we can find a TMcantraction that deletes three lines py, uq and uq. or~~cr, we c;rn relabel p, u axad u if :xxessary so that p # x, II # 1’ and u# 2. uctiion hypot I, Y’ and Z’ can be found which satisfy the proposition for the contracted graph If we now form X, Y and Z by adding ta, K’, Y’ and Z’ point 4 and limx 194,~4 and uq respectivcfy, the proposition holds for T,,. The theorewt follows by induction. z=


f t ] 1. I%ry. On straigtlt line representation of planar graphs, Ac*a Sci. Math. ISzeged) 11 (1948) 229-233. K!] F. H;uary, Graph Theory (Addison-Wesley, Reading, Mass., 1969). The FousColar Problem (Academic Press, New York, 1967). 14). S. Stein, Cowex maps, Proc. Am. Math. Sot. 2 1395 1) 464-466. 151 K. Wagner, Bemerkunlgen zurn Vierfatbmproblen~, Jber. Deutsch. Math.-Verein. 46 ( 1936) 26- 32.