A Survey on Graph Drawing Beyond Planarity <s> Constraints. <s> Abstract The book thickness bt ( G ) of a graph G is defined, its basic properties are delineated, and relations are given with other invariants such as thickness, genus, and chromatic number. A graph G has book thickness bt ( G ) ≤ 2 if and only if it is a subgraph of a hamiltonian planar graph, but we conjecture that there are planar graphs with arbitrarily high book thickness. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Constraints. <s> Two kinds of new methods are developed to obtain effective representations of hierarchies automatically: theoretical and heuristic methods. The methods determine the positions of vertices in two steps. First the order of the vertices in each level is determined to reduce the number of crossings of edges. Then horizontal positions of the vertices are determined to improve further the readability of drawings. The theoretical methods are useful in recognizing the nature of the problem, and the heuristic methods make it possible to enlarge the size of hierarchies with which we can deal. Performance tests of the heuristic methods and several applications are presented. <s> BIB002
Depending on the type of graph and/or application, additional constraints can be imposed on a drawing. For example, for bipartite graphs, a typical constraint is to represent the vertices of each partition set on one of two parallel lines, which is a fundamental step in the socalled Sugiyama approach for layered drawings BIB002 . Other constraints require that all vertices are collinear in the so-called k-page drawing model BIB001  or co-circular in the circular layout model  . Results about constrained beyond-planar graphs are surveyed in Section 8.