Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Lattice Structures from Planar Graphs. | Lattice Structures from Planar Graphs Stefan Felsner Technische Universitat Berlin Institut fur Mathematik MA 6-1 Strafe des 17. Juni 136 10623 Berlin Germany felsner@ Submitted Dec 2 2002 Accepted Jan 23 2004 Published Feb 14 2004 MR Subject Classifications 05C10 68R10 06A07 Abstract. The set of all orientations of a planar graph with prescribed outdegrees carries the structure of a distributive lattice. This general theorem is proven in the first part of the paper. In the second part the theorem is applied to show that interesting combinatorial sets related to a planar graph have lattice structure Eulerian orientations spanning trees and Schnyder woods. For the Schnyder wood application some additional theory has to be developed. In particular it is shown that a Schnyder wood for a planar graph induces a Schnyder wood for the dual. 1 Introduction This work originated in the study of rigid embeddings of planar graphs and the connections with Schnyder woods. These connections were discovered by Miller 9 and further investigated in 3 . The set of Schnyder woods of a planar triangulation has the structure of a distributive lattice. This was independently shown by Brehm 1 and Mendez 10 . My original objective was to generalize this and prove that the set of Schnyder woods of a 3-connected planar graph also has a distributive lattice structure. The theory developed to this aim turned out to work in a more general situation. In the first half of this paper we present a theory of a-orientations of a planar graph and show that they form a distributive lattice. As noted in 4 this result was already obtained in the thesis of Mendez 10 . Another source for related results is a paper of Propp 13 where he describes lattice structures in the dual setting. The cover relations in Propp s lattices are certain pushing-down operations. These operations were introduced by Mosesian and further studied by Pretzel 11 as reorientations of diagrams of ordered sets. The .
