Orienting planar graphs

✍ Scribed by G.R. Kampen

• Book ID: 103058205
• Publisher: Elsevier Science
• Year: 1976
• Tongue: English
• Weight: 580 KB
• Volume: 14
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(76)90065-0

✦ Synopsis

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~~n of the rule "color point 11 differently frw-n the initia all thiat a graph is oriented by replacing its lines Gth directed lines, 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).