Book Embeddings and Other Linear Layouts for Beyond-Planar Graphs

01.05.2018 bis 28.02.2020

Graph theory is a fundamental branch of computer science, as it finds applications in several areas such as bioinformatics, network analysis, information systems e.t.c. The proposed project will focus on an important problem of graph theory, which is concerned with linear layouts of graphs and dates back to early 1970s. Variants of this problem will be studied in conjunction with graphs beyond planarity, which have recently received a great deal of attention in Graph Drawing. Such graphs typically extend the well-studied planar graphs by posing restrictions on their crossings.
More precisely, in a linear layout the vertices of an input graph are restricted to a line, called spine, and the edges are drawn at different half-planes delimited by the spine, called pages. The most studied variant of linear layouts is the book embedding problem, in which the goal is to find a linear order of the vertices along the spine and an assignment of the edges into a minimum number of required pages (called book thickness or page number or stack number), so that no two edges of the same page cross. A special case of book embeddings are the dispersible embeddings, in which it is additionally required that the graphs induced by the edges of each page to form 1-regular graphs (i.e., matchings). In the “dual” concept of book embeddings, so-called queue layouts, edges of the same page are allowed to cross, as long as no two independent edges nest each other. Here, the minimum number of required pages is called queue number. A variant which naturally extends both the book embeddings and the queue layouts are the mixed linear layouts, in which one allows both types of pages, i.e., (i) where nestings are allowed and crossings are forbidden (stack pages), and (ii) where crossings are allowed and nestings are forbidden (queue pages).
While a large body of research has been devoted to the study of different types of linear layouts for planar graphs, the known results for non-planar graphs are significantly fewer. Most of them either focus on complete and complete bipartite graphs or they are mainly meta-theorems that hold, e.g., for graphs of bounded tree-width, or for minor-closed graphs. In the light of this, we propose the study of different types of linear layouts for classes of graphs beyond-planarity, as those graphs have several interesting structural properties. While the focus will be mainly on 1-planar graphs and 2-planar graphs (which disallow an edge to be crossed more than one and two times, respectively), the study is expected to extend to other classed of beyond planar graphs, e.g., to fan-planar (which disallow a single edge to be crossed by two independent) and RAC graphs (which allow edge crossings only at right angles).