Search

Given a graph G and an integer b , OrthogonalPlanarity is the problem of testing whether G admits a planar orthogonal drawing with at most b bends. OrthogonalPlanarity is known to be NP -complete. We show that this problem belongs to the XP class when parameterized by treewidth. The proof exploits a fixed-parameter tractable approach that uses two more parameters besides treewidth, namely the natural parameter b and the number of vertices with degree at most two of G. Such approach is based on the new concept of sketched orthogonal representation, which synthetically describes a family of equivalent orthogonal drawings. The approach is general enough to be applicable to other related problems, namely HV-Planarity and FlexDraw. Also, in the special case of series-parallel graphs we obtain that both OrthogonalPlanarity and HV-Planarity can be solved in O (n 3 log ⁡ n) time, which improves on the previous O (n 4) bounds for these two. [ABSTRACT FROM AUTHOR]

We introduce and study a constrained planarity testing problem, called 1 -Fixed Constrained Planarity , and prove that this problem can be solved in quadratic time for biconnected graphs. Our solution is based on a novel definition of fixedness that makes it possible to simplify and extend known techniques about Simultaneous PQ-Ordering. We exploit this result to study different versions of the hybrid planarity testing problem. Namely, we show polynomial-time solutions for a variant of NodeTrix Planarity with fixed sides, for PolyLink Planarity , and for Clique Planarity with fixed sides. [ABSTRACT FROM AUTHOR]

Graph Drawing Beyond Planarity is a rapidly growing research area that classifies and studies geometric representations of nonplanar graphs in terms of forbidden crossing configurations. The aim of this survey is to describe the main research directions in this area, the most prominent known results, and some of the most challenging open problems. [ABSTRACT FROM AUTHOR]

We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant k. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be chosen arbitrarily. We show that NodeTrix planarity testing with fixed sides can be solved in O (k 3 k + 3 2 · n) time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in O(n) time for k = 2 , but it is NP-complete for any k > 2 . NodeTrix planarity testing remains NP-complete also in the free sides model when k > 4 . [ABSTRACT FROM AUTHOR]

Abstract An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing , that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. Highlights • HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3. • Polynomial-time HV-planarity testing for 2-connected series-parallel graphs. • Polynomial-time HV-planarity testing for partial 2-trees. [ABSTRACT FROM AUTHOR]

Let ε, ε be two non negative numbers. An approximate rectangle of influence drawing (also called ( ε, ε)-RID) is a proximity drawing of a graph such that: (i) if u, v are adjacent vertices then their rectangle of influence 'scaled down' by the factor $\frac{1}{1+\varepsilon_{1}}$ does not contain other vertices of the drawing; (ii) if u, v are not adjacent, then their rectangle of influence 'blown-up' by the factor 1+ ε contains some vertices of the drawing other than u and v. Firstly, we prove that all planar graphs have an ( ε, ε)-RID for any ε>0 and ε>0, while there exist planar graphs which do not admit an ( ε,0)-RID and planar graphs which do not admit a (0, ε)-RID. Then, we investigate (0, ε)-RIDs; we prove that both the outerplanar graphs and a suitably defined family of graphs without separating 3-cycles admit this type of drawing. Finally, we study polynomial area approximate rectangle of influence drawings and prove that (0, ε)-RIDs of proper track planar graphs (a superclass of the outerplanar graphs) can be computed in polynomial area for any ε>2. As for values of ε such that ε≤2, we describe a drawing algorithm that computes (0, ε)-RIDs of binary trees in area $O(n^{c + f(\varepsilon_{2})})$, where c is a positive constant, f( ε) is a poly-logarithmic function that tends to infinity as ε tends to zero, and n is the number of vertices of the input tree. [ABSTRACT FROM AUTHOR]

It is proved that every series-parallel digraph whose maximum vertex degree is Δ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of Δ distinct slopes. The construction is worst-case optimal in terms of the number of slopes, and it gives rise to drawings with optimal angular resolution π Δ. A variant of the drawing algorithm is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) 1-bend planar drawing with ⌈ Δ 2 ⌉ distinct slopes if biconnected, and with ⌈ Δ 2 ⌉ + 1 distinct slopes if connected. [ABSTRACT FROM AUTHOR]

We establish new results on the curve complexity of k -colored point-set embeddings when k = 3. We show that there exist 3-colored caterpillars with only three independent edges whose 3-colored point-set embeddings may require Ω (n 1 3 ) bends on Ω (n 2 3 ) edges. This settles an open problem by Badent et al. [5] about the curve complexity of point set embeddings of k -colored trees and it extends a lower bound by Pach and Wenger [35] to the case that the graph only has O (1) independent edges. Concerning upper bounds, we prove that any 3-colored path admits a 3-colored point-set embedding with curve complexity at most 4. In addition, we introduce a variant of the k -colored simultaneous embeddability problem and study its relationship with the k -colored point-set embeddability problem. [ABSTRACT FROM AUTHOR]

We study the problem of representing topological graphs as polyline drawings with few bends per edge and such that the topology of the graph is either fully or partially preserved. More formally, let G be a simple topological graph and let Γ be a polyline drawing of G. Drawing Γ partially preserves the topology of G if it has the same external boundary, the same circular order of the edges around each vertex, and the same set of crossings as G , while it fully preserves the topology of G if the planarization of G and the planarization of Γ have the same planar embedding. We prove that if the set of crossing-free edges of G forms a biconnected (connected) spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most one (three), i.e., with at most one (three) bend(s) per edge. If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Ω (n) , while it is O (1) if the number of connected components is O (1). Concerning drawings that fully preserve the topology, we show that if G is k -skew (i.e., it becomes planar after removing k suitably chosen edges), it admits one such drawing with curve complexity at most 2 k ; for 1-skew graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs (i.e., with at most two crossings per edge and maximum edge density), for which we discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology. [ABSTRACT FROM AUTHOR]

We prove that every set of Δ - 1 slopes is 1-bend universal for the planar graphs with maximum vertex degree Δ . This means that any planar graph with maximum degree Δ admits a planar drawing with at most one bend per edge and such that the slopes of the segments forming the edges can be chosen in any given set of Δ - 1 slopes. Our result improves over previous literature in three ways: Firstly, it improves the known upper bound of 3 2 (Δ - 1) on the 1-bend planar slope number; secondly, the previously known algorithms compute 1-bend planar drawings by using sets of O (Δ) slopes that may vary depending on the input graph; thirdly, while these algorithms typically minimize the slopes at the expenses of constructing drawings with poor angular resolution, we can compute drawings whose angular resolution is at least π Δ - 1 , which is worst-case optimal up to a factor of 3 4 . Our proofs are constructive and give rise to a linear-time drawing algorithm. [ABSTRACT FROM AUTHOR]

Abstract We show that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any ϵ > 0 there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than 2 − ϵ. We also show that this ratio cannot be bounded if the embeddings of the outerplanar graphs are given. [ABSTRACT FROM AUTHOR]

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]

A simple topological graph is k -quasiplanar (k ≥ 2) if it contains no k pairwise crossing edges, and k -planar if no edge is crossed more than k times. In this paper, we explore the relationship between k -planarity and k -quasiplanarity to show that, for k ≥ 2 , every k -planar simple topological graph can be transformed into a (k + 1) -quasiplanar simple topological graph. [ABSTRACT FROM AUTHOR]

Visibility representations are a well-known paradigm to represent graphs. From a high-level perspective, a visibility representation of a graph G maps the vertices of G to non-overlapping geometric objects and the edges of G to visibilities, i.e., segments that do not intersect any geometric object other than at their end-points. In this paper, we initiate the study of 2.5D box visibility representations (2.5D-BRs) where vertices are mapped to 3D boxes having the bottom face in the plane z = 0 and edges are unobstructed lines of sight parallel to the x - or y -axis. We prove that: ( i ) Every complete bipartite graph admits a 2.5D-BR; ( i i ) The complete graph K n admits a 2.5D-BR if and only if n ⩽ 19 ; ( i i i ) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBRs), which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n -vertex graph that admits a 2.5D-GBR has at most 4 n − 6 n edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete (the footprint of a 2.5D-BR Γ is the set of bottom faces of the boxes in Γ). [ABSTRACT FROM AUTHOR]

Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete graphs, complete bipartite graphs, multipartite graphs, bounded degree graphs, and genus-1 graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittability in linear time, for a constant k. [ABSTRACT FROM AUTHOR]

A 1 -plane graph is a graph embedded in the plane such that each edge is crossed at most once. A NIC-plane graph is a 1-plane graph such that any two pairs of crossing edges share at most one end-vertex. An edge partition of a 1-plane graph G is a coloring of the edges of G with two colors, red and blue, such that both the graph induced by the red edges and the graph induced by the blue edges are plane graphs. We prove the following: ( i ) Every NIC-plane graph admits an edge partition such that the red graph has maximum vertex degree three; this bound on the vertex degree is worst-case optimal. ( ii ) Deciding whether a NIC-plane graph admits an edge partition such that the red graph has maximum vertex degree two is NP-complete. ( iii ) Deciding whether a 1-plane graph admits an edge partition such that the red graph has maximum vertex degree one, and computing one in the positive case, can be done in quadratic time. Applications of these results to graph drawing are also discussed. [ABSTRACT FROM AUTHOR]

We give new results about the relationship between 1-planar graphs and RAC graphs . A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs , the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i.e., no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar. [ABSTRACT FROM AUTHOR]

A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. It is known that the problem of testing 1-planarity of a graph is NP-complete. In this paper, we study outer-1-planar graphs. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a given graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists. [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]

In a visibility representation of a graph G , the vertices are represented by non-overlapping geometric objects, while the edges are represented as segments that only intersect the geometric objects associated with their end-vertices. Given a set P of n points, an Anchored Visibility Representation of a graph G with n vertices is a visibility representation such that for each vertex v of G , the geometric object representing v contains a point of P. We prove positive and negative results about the existence of anchored visibility representations under various models, both in 2D and in 3D space. We consider the case when the mapping between the vertices and the points is not given and the case when it is only partially given. [ABSTRACT FROM AUTHOR]