Abstract
In this master thesis we study simple drawings. Simple drawings are drawings of graphs in the plane that fulfill some properties, which restrict their crossings.
We are interested in the information that rotation systems can offer about crossings. Rotation systems of simple drawings give us the order in which edges leave the vertices. It is known that rotation systems of simple drawings of complete graphs determine which edges cross. We study what information we can gain from rotation systems of other types of graphs. We show that rotation systems of simple drawings of graphs with one edge less than the complete graph determine the number of crossings. Moreover, we proof that rotation systems of simple drawings of graphs with n≥5 vertices and minimal degree of at least (n2) determine the number of crossings. Furthermore, we show that rotation systems of simple drawings of K_{2,3} determine the parity of the number of crossings. It is known that the number of crossings in simple drawings of K_{m,n} with m and n fixed and both odd always have the same parity.
We also focus on the question of whether simple drawings of complete bipartite graphs contain plane spanning trees. We show that simple drawings of K_{2,n} and K_{3,n} as well as some special types of simple drawings of K_{m,n} do. Those special types are outer drawings, straightline drawings, 2page book drawings, and circular drawings. We show that all those simple drawings contain a particular type of plane spanning tree that we call shooting star. Shooting stars are plane spanning trees that contain all edges incident to one vertex.
We are interested in the information that rotation systems can offer about crossings. Rotation systems of simple drawings give us the order in which edges leave the vertices. It is known that rotation systems of simple drawings of complete graphs determine which edges cross. We study what information we can gain from rotation systems of other types of graphs. We show that rotation systems of simple drawings of graphs with one edge less than the complete graph determine the number of crossings. Moreover, we proof that rotation systems of simple drawings of graphs with n≥5 vertices and minimal degree of at least (n2) determine the number of crossings. Furthermore, we show that rotation systems of simple drawings of K_{2,3} determine the parity of the number of crossings. It is known that the number of crossings in simple drawings of K_{m,n} with m and n fixed and both odd always have the same parity.
We also focus on the question of whether simple drawings of complete bipartite graphs contain plane spanning trees. We show that simple drawings of K_{2,n} and K_{3,n} as well as some special types of simple drawings of K_{m,n} do. Those special types are outer drawings, straightline drawings, 2page book drawings, and circular drawings. We show that all those simple drawings contain a particular type of plane spanning tree that we call shooting star. Shooting stars are plane spanning trees that contain all edges incident to one vertex.
Original language  English 

Supervisors/Advisors 

Publication status  Published  2019 
Keywords
 simple drawings
 rotation systems
 ; spanning trees
Fields of Expertise
 Information, Communication & Computing