Search

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]

An ortho-polygon visibility representation (OPVR) of an embedded graph G is an embedding-preserving drawing that maps each vertex of G to a distinct orthogonal polygon and each edge of G to a vertical or horizontal visibility between its end-vertices. An OPVR Γ has vertex complexity k if every polygon of Γ has at most k reflex corners. A 1-plane graph is an embedded graph such that each edge is crossed at most once. It is known that 3-connected 1-plane graphs admit an OPVR with vertex complexity at most 12, while vertex complexity at least 2 may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity 5 is always sufficient, while vertex complexity 4 may be sometimes required. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in 3-connected 1-plane graphs. An implication of the upper bound is the existence of a O ˜ (n 10 7 ) -time drawing algorithm that computes an OPVR of an n -vertex 3-connected 1-plane graph on an integer grid of size O (n) × O (n) and with vertex complexity at most 5. [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]

A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red–blue edge coloring of an optimal 1-plane graph G partitions the edge set of G into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: ( i ) Every optimal 1-plane graph has a red–blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. ( ii ) A red–blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed. [ABSTRACT FROM AUTHOR]

Let 〈 G r , G b 〉 be a pair of plane st -graphs with the same vertex set V . A simultaneous visibility representation with L-shapes of 〈 G r , G b 〉 is a pair of bar visibility representations 〈 Γ r , Γ b 〉 such that, for every vertex v ∈ V , Γ r ( v ) and Γ b ( v ) are a horizontal and a vertical segment, respectively, which share an end-point. In other words, every vertex is drawn as an L-shape, every edge of G r is a vertical visibility segment, and every edge of G b is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: (i) a characterization of those pairs of plane st -graphs admitting such a representation, (ii) a quadratic time algorithm to recognize them, and (iii) a linear time drawing algorithm if the test is positive. As an application, starting from a simultaneous visibility representation with L-shapes, we show how to compute a simultaneous embedding of the two graphs with at most two bends per edge and right-angle crossings. [ABSTRACT FROM AUTHOR]

• For n ≥ 14 there is a properly 2-colored SP-graph with 2 n + 4 vertices s.t. any 2-colored PSE requires Ω (n) bends on Ω (n) edges • 2 bends per edge suffice for a 2-colored PSE of properly 2-colored outerplanar graphs • 1 bend per edge suffices for a 2-colored PSE of a properly 2-colored outerplanar graph if the points are linearly separable • 3 bends per edge suffice for a 2-colored PSE of a 2-colored outerplanar graph • 1 bend per edge suffices for a 2-colored PSE of a 2-colored caterpillar Let G be a planar graph whose vertices are colored either red or blue and let S be a set of points having as many red (resp. blue) points as the red (resp. blue) vertices of G. A 2-colored point-set embedding of G on S is a planar drawing that maps each red (resp. blue) vertex of G to a red (resp. blue) point of S. We show that there exist partial 2-trees that are properly 2-colored (i.e., they are 2-colored with no two adjacent vertices have the same color), whose point-set embeddings may require linearly many bends on linearly many edges. For a contrast, we show that two bends per edge are sufficient for 2-colored point-set embedding of properly 2-colored outerplanar graphs. For separable point sets this bound reduces to one, which is worst-case optimal. If the 2-coloring of the outerplanar graph is not proper, three bends per edge are sufficient and one bend per edge (which is worst-case optimal) is sufficient for caterpillars. [ABSTRACT FROM AUTHOR]

We present a new model for hybrid planarity that relaxes existing hybrid representation models. A graph G = (V , E) is (k , p) -planar if V can be partitioned into clusters of size at most k such that G admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region ; (ii) cluster regions are pairwise disjoint, (iii) each vertex v ∈ V is identified with at most p distinct points, called ports , on the boundary of its cluster region; (iv) each inter-cluster edge (u , v) ∈ E is identified with a Jordan arc connecting a port of u to a port of v ; (v) inter-cluster edges do not cross or intersect cluster regions except at their end-points. We first tightly bound the number of edges in a (k , p) -planar graph with p < k. We then prove that (4 , 1) -planarity testing and (2 , 2) -planarity testing are NP-complete problems. Finally, we prove that neither the class of (2 , 2) -planar graphs nor the class of 1-planar graphs contains the other, indicating that the (k , p) -planar graphs are a large and novel class. [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]

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 k-spine, h-bend planar drawings in which each vertex of a planar graph G lies on one of horizontal lines and each edge of G is drawn as a polyline containing at most bends. A graph with a k-spine, h-bend planar drawing is said to be k-spine, h-bend planar. We mainly focus on k-spine, 1-bend planar drawings, showing that for each , there exists a planar graph that is not k-spine, 1-bend planar, and furthermore, that it is -hard to test k-spine, 1-bend planarity. Given this complexity result, we further narrow our focus onto 2-spine, 1-bend planar drawings. We characterize 2-spine, 1-bend planarity using a new generalization of Hamiltonian graphs that we call Hamiltonian-with-handles graphs. We observe that our characterization naturally extends the connection between 2-page book embeddings and Hamiltonicity. Finally, we use our characterization to show that 2-outerplanar graphs are 2-spine, 1-bend planar. [Copyright &y& Elsevier]

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]