On Geometric Drawings of Graphs

combinatorics;crossing numbers;graph theory;graph;drawing;complete graph;rectilinear;graph embedding;graph drawing

Arroyo Guevara, Alan Marceloaffiliation1:Faculty of Mathematics ; advisor:Richter, Bruce ; Richter, Bruce ;

University of Waterloo

关键词: crossing numbers;    graph theory;    drawing;    graph embedding;    graph drawing;    complete graph;    Doctoral Thesis;    graph;    combinatorics;    rectilinear;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/13103/3/ArroyoGuevara_AlanMarcelo.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

This thesis is about geometric drawings of graphs and their topological generalizations. First, we study pseudolinear drawings of graphs in the plane. A pseudolinear drawing is onein which every edge can be extended into an infinite simple arc in the plane,homeomorphic to $mathbb{R}$, and such that every two extending arcs cross exactly once. This is a natural generalization of the well-studied class of rectilinear drawings, where edges are straight-line segments. Although, the problem of deciding whether a drawing is homeomorphic to a rectilinear drawing is NP-hard, in this work we characterize the minimal forbidden subdrawings for pseudolinear drawings and we also provide a polynomial-time algorithm for recognizing this family of drawings.Second, we consider the problem of transforming a topological drawing into a similar rectilinear drawing preserving the set of crossing pairs of edges. We show that, under some circumstances,pseudolinearity is a necessary and sufficient condition for the existence of such transformation. For this, we prove a generalization of Tutte's Spring Theorem for drawings with crossings placed in a particular way.Lastly, we study drawings of $K_n$ in the sphere whose edges can be extended to an arrangement of pseudocircles. Anarrangement of pseudocircles is a set of simple closed curves in the sphere such that every two intersect at most twice. We show that (i) there is drawing of $K_{10}$ that cannot be extended into an arrangement of pseudocircles; and (ii) there is a drawing of $K_9$ that can be extended to an arrangement of pseudocircles, but no extension satisfies that every two pseudocircles intersects exactly twice. We also introduce the notionpseudospherical drawings of $K_n$, a generalization ofspherical drawings in which each edge is a minor arc of a great circle. We show that these drawings are characterized by a simple local property. We also show that every pseudospherical drawing has an extension into an arrangement of pseudocircles where the ``at most twice'' condition is replaced by ``exactly twice''.