Search

We study the complexity of testing whether a biconnected graph G = (V , E) is planar with the constraint that some cyclic orders of the edges incident to its vertices are allowed while some others are forbidden. The allowed cyclic orders are described by associating every vertex v of G with a set D (v) of FPQ-trees. Let tw be the treewidth of G and let D max be the maximum number of FPQ-trees per vertex. We show that the problem is FPT when parameterized by tw + D max , paraNP-hard when parameterized by D max , and W[1]-hard when parameterized by tw. We also consider NodeTrix planar representations of clustered graphs, where clusters are adjacency matrices and inter-cluster edges are non-intersecting simple curves. We prove that NodeTrix planarity with fixed sides is FPT when parameterized by the size of clusters plus the treewidth of the graph obtained by collapsing clusters to single vertices, provided that this graph is biconnected. [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]

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]

A subcubic planar graph is a planar graph whose vertices have degree at most 3. We show that the subcubic planar graphs with at least five vertices have planar slope number at most 4, which is worst-case optimal. This answers an open question by Jelínek et al. [10] . Furthermore, we prove that the subcubic planar graphs with at least five vertices have angular resolution π / 4 , which solves an open problem by Kant [11] and by Formann et al. [8] . [ABSTRACT FROM AUTHOR]

Let G be a 3-connected planar graph with n vertices and let p ( G ) be the maximum number of vertices of an induced subgraph of G that is a path. Substantially improving previous results, we prove that p ( G ) ≥ log ⁡ n 12 log ⁡ log ⁡ n . To demonstrate the tightness of this bound, we notice that the above inequality implies p ( G ) ∈ Ω ( ( log 2 ⁡ n ) 1 − ε ) , where ε is any positive constant smaller than 1, and describe an infinite family of planar graphs for which p ( G ) ∈ O ( log ⁡ n ) . As a byproduct of our research, we prove a result of independent interest: Every 3-connected planar graph with n vertices contains an induced subgraph that is outerplanar and connected and that contains at least n 3 vertices. The proofs in the paper are constructive and give rise to O ( n ) -time algorithms. [ABSTRACT FROM AUTHOR]

Abstract: A Right Angle Crossing Graph (also called a RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A -planar graph is a graph that has a drawing where every edge is crossed at most once. This paper studies the combinatorial relationship between the family of RAC graphs and the family of -planar graphs. It is proved that: (1) all RAC graphs having maximal edge density belong to the intersection of the two families; and (2) there is no inclusion relationship between the two families. As a by-product of the proof technique, it is also shown that every RAC graph with maximal edge density is the union of two maximal planar graphs. [Copyright &y& Elsevier]

This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h = 4 and G is a simple 3-plane graph, while it can be solved in linear time when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity. [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]

A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A k-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most k bends and edges cross only at right angles. A graph is k-bend RAC if it has a k -bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing) . The relationships between 1-planar and k -bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: ( i ) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? ( i i ) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs. [ABSTRACT FROM AUTHOR]

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 area using a sub-linear number of crossings per edge, and that for any given number , every outerplanar graph admits an area drawing with 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. [Copyright &y& Elsevier]

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]

A drawing of a graph such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line is called a 2 -page drawing. If all edges are in the same half-plane, the drawing is called a 1 -page drawing. We want to compute 1 -page and 2 -page drawings of planar graphs such that the number of crossings per edge does not depend on the number of vertices. We show that for any constant k , there exist planar graphs that require more than k crossings per edge in both 1 -page and 2 -page drawings. We then prove that if the vertex degree is bounded by Δ , every planar 3-tree has a 2 -page drawing with a number of crossings per edge that only depends on Δ . Finally, we show a similar result for 1 -page drawings of partial 2 -trees. [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]

Abstract: A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if addition of any edge destroys 1-planarity of G. We first study combinatorial properties of maximal 1-planar embeddings. In particular, we show that in a maximal 1-planar embedding, the graph induced by the non-crossing edges is spanning and biconnected. Using the properties, we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system Φ (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding ξ of G that is consistent with the given rotation system Φ. Our algorithm also produces such an embedding in linear time, if it exists. [Copyright &y& Elsevier]