Search

We study the problem of computing drawings of planar graphs in sub-quadratic area, by allowing edge crossings. We first prove that sub-quadratic area cannot be achieved if only a constant number of crossings per edge is allowed. More precisely, we show that the same area lower bounds as in the crossing-free case hold for straight-line and poly-line drawings of planar graphs and seriesparallel graphs. Motivated by this result, we study straight-line drawings of planar graphs where the number of crossings per edge is not bounded by a constant. In this case, we prove that every planar graph admits a straight-line drawing with sub-quadratic area and sub-linear thickness (the thickness of a drawing is the minimum number of colors that can be assigned to the edges so that each color class induces a planar drawing). We also prove that every partial 2-tree (and hence every series-parallel graph) admits a linear-area straight-line drawing with thickness at most 10. It is worth remarking that a drawing with thickness h - 1 is h-quasi planar, i.e. it does not contain h-mutually crossing edges. The main ingredient to prove our results is (c, t)-track layouts, a combinatorial tool that can be represented as a drawing where: (i) each vertex is assigned to one of t horizontal layers (tracks), (ii) no two adjacent vertices are on the same track, (iii) each edge receives one of c colors, so that no two edges of the same color (u, v) and (w, z) cross if u, w are on the same track, and v, z are on the same track. [ABSTRACT FROM AUTHOR]

A simultaneous geometric embedding (SGE) of two planar graphs G1 and G2 with the same vertex set is a pair of straight-line planar drawings Γ1 of G1 and Γ2 of G2 such that each vertex is drawn at the same point in Γ1 Γ2. Many papers have been devoted to the study of which pairs of graphs admit a SGE, and both positive and negative results have been proved. We extend the study of SGE, by introducing and characterizing a new class of planar graphs that makes it possible to immediately extend several positive results that rely on the property of strictly monotone paths. Moreover, we introduce a relaxation of the SGE setting where Γ1 and Γ2 are required to be quasi-planar (i.e. they can have crossings provided that there are no three mutually crossing edges). This relaxation allows for the simultaneous embedding of pairs of planar graphs that are not simultaneously embeddable in the classical SGE setting and opens up several new interesting research questions. [ABSTRACT FROM AUTHOR]

A2-layer drawing of a bipartite graph G is a drawing such that the vertices of each partition set are drawn as points of a distinct horizontal line (called a layer) and the edges are drawn as straight-line segments. We study 2-layer drawings where edges can cross only at right angles; these drawings are called 2-layer right angle crossing drawings (2-layer RAC drawings for short). We focus on the following problem, which we call the maximum 2-layer RAC subgraph (M2LRacS) problem. Given a bipartite graph G, compute a subgraph H of G such that: (i) H admits a 2-layer RAC drawing and (ii) H has the maximum number of edges among the subgraphs of G that satisfy (i). We study this problem both in the no-fixed-layer setting, where no restriction is given on the vertex ordering on each layer, and in the 1-?xed-layer setting, where the ordering of the vertices of one of the two layers is given as part of the input and cannot be changed. The M2LRacS problem is known to be NP-hard in the no-fixed-layer setting (Di Giacomo, E., Didimo, W., Eades, P. and Liotta, G. (2011) 2-Layer Right Angle Crossing Drawings. Proc. IWOCA 2011, Lecturer Notes in Computer Science 7056, pp. 156-169; Di Giacomo, E., Didimo, W., Eades, P. and Liotta, G. (2014) 2-layer right angle crossing drawings. Algorithmica, 68, 954-997), but no algorithm has been proposed so far to solve it. We prove that the M2LRacS problem remains NP-hard even in the 1-?xed-layer setting, and provide different heuristics to solve it in the two settings; one of these heuristics is a 3-approximation algorithm for the no-fixed-layer setting. Also, we present the results of an experimental study that compares our heuristics and shows the effectiveness of the 3-approximation algorithm in practice. [ABSTRACT FROM AUTHOR]