A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> Abstract : Minimizing the area of a circuit is an important problem in the domain of Very Large Scale Integration. We use a theoretical VLSI model to reduce this problem to one of laying out a graph, where the transistors and wires of the circuit are identified with the vertices and edges of the graph. We give an algorithm that produces VLSI layouts for classes of graphs that have good separator theorems. We show in particular that any planar graph of n vertices has an O(n lg-square(n)) area layout and that any tree of n vertices can be laid out in linear area. The algorithm maintains a sparse representation for layouts that is based on the well-known UNION-FIND data structure, and as a result, the running time devoted to management of this representation is nearly linear. (Author) <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed. Since even for some natural patterns graphs containing m connections may require Ω(m2) area, in order to achieve compact embeddings restricted classes of graphs have to be considered. For example, arbitrary trees (of bounded degree) can be embedded in linear area without edges crossing over. Planar graphs can be embedded efficiently only if crossovers are allowed in the embedding. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fary embedding (i.e., straight-line embedding) on the 2n−4 byn−2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fary embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> We show that each plane graph of order n 2 3 has a straight line embedding on the n-2 by n-2 grid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> It is proved that every k-colourable graph on n vertices has a grid drawing with O(kn) area, and that this bound is best possible. This result can be viewed as a generalisation of the no-three-in-line problem. A further area bound is established that includes the aspect ratio as a parameter. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> We study how much better a right-angled crossing (RAC) drawing of a planar graph can be than any planar drawing of the same planar graph. We analyze the area requirement, the edge-length ratio, and the angular resolution. For the first two measures, a RAC drawing can be arbitrarily much better, whereas for the third measure a RAC drawing can be 2.75 times as good. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> Note: Special Issue on Selected Papers from GD '09. Accepted, subject to minor revisions Reference EPFL-ARTICLE-158708 Record created on 2010-11-26, modified on 2017-05-12 <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> This paper describes algorithms for computing non-planar drawings of planar graphs in subquadratic area such that: (i) edge crossings are allowed only if they create large angles; (ii) the maximum number of bends per edge is bounded by a (small) constant. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> We study the problem of computing h-quasi planar drawings in linear area; in an h-quasi planar drawing the number of mutually crossing edges is at most h−1. We prove that every n-vertex partial k-tree admits a straight-line h-quasi planar drawing in O(n) area, where h depends on k but not on n. For specific sub-families of partial k-trees, we present ad-hoc algorithms that compute h-quasi planar drawings in linear area, such that h is significantly reduced with respect to the general result. Finally, we compare the notion of h-quasi planarity with the notion of h-planarity, where each edge is allowed to be crossed at most h times. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> Abstract In this paper we study how to compute compact straight-line drawings of planar graphs with a limited number of crossings per edge. We prove that every outerplanar graph can be drawn in O ( n log n ) area using a sub-linear number of crossings per edge, and that for any given number e > 0 , every outerplanar graph admits an O ( n 1 + e ) area drawing with O ( n 1 − e ) crossing per edge. The drawing algorithms run in linear time and can be also generalized to another meaningful sub-family of series–parallel graphs with bounded vertex-degree. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> Area-Crossing Tradeoffs for Planar Graphs <s> A k-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets such that no two edges that are in the same set are nested with respect to the vertex ordering. A k-track layout of a graph consists of a vertex k-colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The queue-number (track-number) of a graph G, is the minimum k such that G has a k-queue (k-track) layout.This paper proves that every n-vertex planar graph has track number and queue number at most O ( log ? n ) . This improves the result of Di Battista, Frati, and Pach (2013) 5 who proved the first sub-polynomial bounds on the queue number and track number of planar graphs. Specifically, they obtained O ( log 2 ? n ) queue number and O ( log 8 ? n ) track number bounds for planar graphs.The result also implies that every planar graph has a 3D crossing-free grid drawing in O ( n log ? n ) volume. The proof uses a non-standard type of graph separators. <s> BIB011
The area requirement of planar straight-line drawings is a widely investigated problem. Motivated by VLSI applications, seminal papers studied how to compute area-efficient graph layouts BIB001 BIB002 . Different popular results establish that an n-vertex planar graph can always be drawn with straight-line edges in O (n 2 ) area BIB003 BIB004 . This bound is worst-case optimal for the family of planar graphs as there are infinitely many planar graphs whose planar drawings require quadratic area BIB003 . Several attempts have been made to prove the existence of straight-line planar drawings with o(n 2 ) area for specific subfamilies of planar graphs, such as trees, outerplanar graphs, and series-parallel graphs (see, e.g., BIB010 for references on these results). A natural question that arises from the aforementioned results is whether allowing some edge crossings may help to reduce the area of a drawing of a planar graph. In other words, what is the area requirement of beyond-planar drawings of planar graphs? Wood shows that, for any fixed positive integer k > 0, all k-colorable graphs have a straight-line drawing in linear area; this implies that planar graphs always admit O (n) area straight-line drawings with crossing edges BIB005 . However, the technique by Wood can give rise to drawings where some edges contain a linear number of crossings and the angles at which two edges cross can be arbitrarily small. The use of edge crossings that form large angles is studied in different papers. Straight-line RAC drawings of planar graphs may require Ω(n 2 ) area BIB007 , thus right angle crossing drawings do not help to reduce the area requirement bound for planar graphs in the general case. On the positive side, for infinitely many values of n, there exists an n-vertex planar graph whose requirement is Θ(n 2 ) for straight-line planar drawings and Θ(n) for straight-line RAC drawings BIB006 . Analogous results hold for other quality metrics such as uniform edge length and angular resolution BIB006 . In addition, every planar graph admits an ACLα drawing with two bends per edge in O (n 5 3 ) area BIB008 , and every planar graph with vertex-degree at most Δ admits a 4-bend RAC drawing in O (n √ Δn) area BIB008 . Note that, if Δ is a sublinear function of n, these RAC drawings have subquadratic area. Compact nonplanar drawings of planar graphs with a constant or sublinear number of crossings per edge are also studied BIB010 . Every n-vertex outerplanar graph admits a straight-line drawing with O ( n log n ) crossings per edge in O (n log n) area. Also, for any given ϵ > 0, every n-vertex outerplanar graph admits a straight-line drawing with O (n 1−ϵ ) crossings per edge in O (n 1+ϵ ) area, which Beyond-planar straight-l. k-planar straight-l. k-qasi planar k-bend RAC k-bend ACLα planar Δ denotes the maximum vertex degree. The question mark indicates that bounds better than those for planar drawings are not known. For reasons of space, the table does not report the corresponding references. gives a clear tradeoff scheme between area requirement and number of crossings per edge. These results are based on a linear-time drawing algorithm, which can also be applied to other subfamilies of planar graphs that admit a "level" drawing with specific properties, such as flat series-parallel graphs with bounded degree (see BIB010 ). Nonetheless, if we insist on having a constant number of crossings per edge, planar and nonplanar drawings of planar graphs have in general the same area requirement. This is true even for series-parallel graphs  . On the positive side, every n-vertex planar graph has a straight-line o(n)-quasi planar drawing in o(n 2 ) area. More precisely, by combining drawing techniques in Di Giacomo et al.  with results on the track number of planar graphs BIB011 , one can prove that every n-vertex planar graph admits either a straight-line O (log n)-quasi planar drawing in O (n log 3 n) area or a straight-line O (log 2 n)-quasi planar drawing in O (n log n) area. Also, every partial 2-tree admits a linear-area straight-line drawing with thickness at most 10 and hence a linear-area 11-quasi planar straightline drawing  . Outerplanar graphs and flat series-parallel graphs with bounded vertex degree (which are partial 2-trees) have quasi planar and 5-quasi planar drawings in linear area, respectively BIB009 . Table 8 summarizes the main results presented in this subsection. Open problems. The stretchability problem for beyond-planar graphs is a fertile and essentially unexplored research subject. As a matter of fact, for any type of forbidden crossing configuration, the corresponding stretchability question gives rise to an open problem. For example: Problem 11. Characterize the stretchable k-quasi planar topological graphs (even when k = 3). Another research stream is about embedding-preserving drawings with good crossing angle resolution. This question is interesting even for structurally simple topological graphs. For example: