An outer-string representation of a graph is an intersection representation in which each vertex is represented by a curve that is contained in the unit disk and has at least one endpoint on the boundary of the unit disk. In an outer-1-string representation the curves representing any two vertices are in addition allowed to intersect at most once. In this paper, we consider the following constrained version: Given a graph G plus a cyclic order v1, . . . , vn of the vertices in G, test whether G has an outer-string or an outer-1-string representation in which the curves representing v1, . . . , vn intersect the boundary of the unit disk in this order. We first show that a graph has an outer-string representation for all possible cyclic orders of the vertices if and only if the graph is the complement of a chordal graph. Then we turn towards the situation where one particular cyclic order of the vertices is fixed. We characterize the chordal graphs admitting a constrained outer-string representation and the trees and cycles admitting a constrained outer-1-string representation. The characterizations yield polynomial-time recognition and construction algorithms; in the case of outer-1-string representations the run time is linear. We also show how to decide in polynomial time whether an arbitrary graph admits a constrained L-shaped outer-1-string representation. In an L-shaped representation the curves are 1-bend orthogonal polylines anchored on a horizontal line, and they are contained in the half-plane below that line. However, not even all paths with a constrained outer-1-string representation admit one with L-shapes. We show that 2-bend orthogonal polylines are sufficient for trees and cycles with a constrained outer-1-string representation.

A conforming partition of a rectilinear n -gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i.e., all corners of all rectangles must lie on the boundary of P ). The stabbing number of such a partition is the maximum number of rectangles intersected by an axis-aligned segment lying in the interior of P . In this paper, we examine the problem of computing conforming partitions with low stabbing number. We show that computing a conforming partition with stabbing number at most 4 is NP -hard, which strengthens a previously known hardness result [Durocher & Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)] and eliminates the possibility for fixed-parameter-tractable algorithms parameterized by the stabbing number unless P = NP . In contrast, we give (i) an O ( n log ⁡ n ) -time algorithm to decide whether a conforming partition with stabbing number 2 exists, (ii) a fixed-parameter-tractable algorithm parameterized by both the stabbing number and treewidth of the pixel graph of the polygon, and (iii) a fixed-parameter-tractable algorithm parameterized by the stabbing number for polygons without holes in general position.

The problem of computing vertex and edge connectivity of a graph are classical problems in algorithmic graph theory. The focus of this paper is on computing these parameters for graphs drawn on the plane. A typical example of such graphs are planar graphs which can be embedded without any crossings. It has long been known that vertex and edge connectivity of planar embedded graphs can be computed in linear time. Very recently, Biedl and Murali extended the techniques from planar graphs to 1-plane graphs without ×-crossings, i.e., crossings whose endpoints induce a matching. While the tools used were novel, they were highly tailored to 1-plane graphs, and do not provide much leeway for further extension. In this paper, we develop alternate techniques that are simpler, have wider applications to near-planar graphs, and can be used to test both vertex and edge connectivity. Our technique works for all those embedded graphs where any pair of crossing edges are connected by a path that, roughly speaking, can be covered with few cells of the drawing. Important examples of such graphs include optimal 2-planar and optimal 3-planar graphs, d-map graphs, d-framed graphs, graphs with bounded crossing number, and k-plane graphs with bounded number of ×-crossings.

Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-$k$-planarity is NP-complete already for $k=1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.

We give an algorithm to morph planar graph drawings that achieves small grid size at the expense of allowing a constant number of bends on each edge. The input is an $n$-vertex planar graph and two planar straight-line drawings of the graph on an $O(n) \times O(n)$ grid. The planarity-preserving morph is composed of $O(n)$ linear morphs between successive pairs of drawings, each on an $O(n) \times O(n)$ grid with a constant number of bends per edge. The algorithm to compute the morph runs in $O(n^2)$ time on a word RAM model with standard arithmetic operations -- in particular no square roots or cube roots are required. The first step of the algorithm is to morph each input drawing to a planar orthogonal box drawing where vertices are represented by boxes and each edge is drawn as a horizontal or vertical segment. The second step is to morph between planar orthogonal box drawings. This is done by extending known techniques for morphing planar orthogonal drawings with point vertices.

A graph is called 1-plane if it has an embedding in the plane where each edge is crossed at most once by another edge. A crossing of a 1-plane graph is called an ×-crossing if there are no other edges connecting the endpoints of the crossing (apart from the crossing pair of edges). In this paper, we show how to compute the vertex connectivity of a 1-plane graph G without ×-crossings in linear time. To do so, we show that for any two vertices u,v in a minimum separating set S, the distance between u and v in an auxiliary graph Λ(G) (obtained by planarizing G and then inserting into each face a new vertex adjacent to all vertices of the face) is small. It hence suffices to search for a minimum separating set in various subgraphs Λ_i of Λ(G) with small diameter. Since Λ(G) is planar, the subgraphs Λ_i have small treewidth. Each minimum separating set S then gives rise to a partition of Λ_i into three vertex sets with special properties; such a partition can be found via Courcelle’s theorem in linear time.

The input to the distant representatives problem is a set of n objects in the plane and the goal is to find a representative point from each object while maximizing the distance between the closest pair of points. When the objects are axis-aligned rectangles, we give polynomial time constant-factor approximation algorithms for the L₁, L₂, and L_∞ distance measures. We also prove lower bounds on the approximation factors that can be achieved in polynomial time (unless P = NP).

1-planar graphs are graphs that can be drawn in the plane such that any edge intersects with at most one other edge. Ackerman showed that the edges of a 1-planar graph can be partitioned into a planar graph and a forest, and claims that the proof leads to a linear time algorithm. However, it is not clear how one would obtain such an algorithm from his proof. In this paper, we first reprove Ackerman’s result (in fact, we prove a slightly more general statement) and then show that the split can be found in linear time by using an edge-contraction data structure by Holm, Italiano, Karczmarz, Łącki, Rotenberg and Sankowski.

In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. In this paper, we study fan-planar drawings that use h (horizontal) layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in h, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for h = 2: It was already known how to test the existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper h-layer drawing; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.

The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we show that the crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an $$O(n)\times O(n)$$ O(n)×O(n)-grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3. One crucial ingredient here is that the crossing number of a graph with a separation pair can be lower-bounded using the crossing numbers of its cut-components, a result that may be interesting in its own right. Finally, we give a $$4{\mathbf{w}}^3$$ 4w3-approximation of the crossing number for maximal graphs of pathwidth $${\mathbf{w}}$$ w. This is a constant approximation for bounded pathwidth. We complement this with an NP-hardness proof of the weighted crossing number already for pathwidth 3 graphs and bicliques $$K_{3,n}$$ K3,n.

It is well-known that every planar graph has a Tutte path, i.e., a path $P$ such that any component of $G-P$ has at most three attachment points on $P$. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of $G-P$ have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to $P$. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.

A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence---increasing or decreasing---has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an $x$-monotone polygonal path for which every maximal subpath, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of $n$ distinct real numbers contains a rollercoaster of length at least $\lceil n/2\rceil$ for $n>7$, while the best known lower bound is $\Omega(n/\log n)$. In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the $O(n\log n)$-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of $\{1,\dots,n\}$ can be computed in $O(n\log\log n)$ time. The search for rollercoasters was motivated by the orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is an embedded caterpillar where every vertex has degree either 4 or 1 and such that the two leaves adjacent to each spine vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every $n$-vertex top-view caterpillar on every set of $\frac{25}{3}(n+4)$ points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is $O(n\log n)$. We also show that such a drawing can be obtained in linear time when the points are given in sorted order.

A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence, that is increasing or decreasing, has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as a polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three points. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length subsequence that is a rollercoaster. It was conjectured that every sequence of $n$ distinct real numbers contains a rollercoaster of length at least $\lceil n/2\rceil$ for $n>7$, while the best known lower bound is $Ω(n/\log n)$. In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the $O(n\log n)$-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of $\{1,\dots,n\}$ can be computed in $O(n \log \log n)$ time. The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every $n$-node top-view caterpillar on every set of $\frac{25}{3}n$ points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is $O(n \log n)$. We also show that such a drawing can be obtained in linear time, provided that the points are given in sorted order.

A (weak) rectangle visibility representation, or simply an RVR, of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Given a graph with a fixed embedding in the plane, we show that the problem of testing whether this graph has an embedding-preserving RVR can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs, i.e., for embedded graphs having at most one crossing per edge. The linear time algorithm uses three forbidden configurations, which extend the set known for straight-line drawings of 1-plane graphs. The algorithm first checks for the presence of these forbidden configurations in the input graph, and then either an embedding-preserving RVR is computed (also in linear time) or a forbidden configuration is reported as a negative witness. Finally, we discuss extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.

A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.

Guarding a polygon with few guards is an old and well-studied problem in computational geometry. Here we consider the following variant: We assume that the polygon is orthogonal and thin in some sense, and we consider a point $p$ to guard a point $q$ if and only if the minimum axis-aligned rectangle spanned by $p$ and $q$ is inside the polygon. A simple proof shows that this problem is NP-hard on orthogonal polygons with holes, even if the polygon is thin. If there are no holes, then a thin polygon becomes a tree polygon in the sense that the so-called dual graph of the polygon is a tree. It was known that finding the minimum set of $r$-guards is polynomial for tree polygons, but the run-time was $\tilde{O}(n^{17})$. We show here that with a different approach the running time becomes linear, answering a question posed by Biedl et al. (SoCG 2011). Furthermore, the approach is much more general, allowing to specify subsets of points to guard and guards to use, and it generalizes to polygons with $h$ holes or thickness $K$, becoming fixed-parameter tractable in $h+K$.

In this paper, we prove that every planar graph has a 1-string B_2-VPG representation - a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices u, v intersect precisely once whenever there is an edge between u and v.

We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.

We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.

We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in O(nlog⁡n) time and O(n) space, where n denotes the number of vertices of the polygon.

We give an algorithm to morph between two planar orthogonal drawings of a graph, preserving planarity and orthogonality. The morph uses a quadratic number of steps, where each step is a linear morph (a linear interpolation between two drawings). This is the first algorithm to provide planarity-preserving morphs with well-behaved complexity for a significant class of graph drawings. Our method is to morph until each edge is represented by a sequence of segments, with corresponding segments parallel in the two drawings. Then, in a result of independent interest, we morph such parallel planar orthogonal drawings, preserving edge directions and planarity.

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight.

In this paper, we study the point-set-embeddability-problem, i.e., given a planar graph and a set of points, is there a mapping of the vertices to the points such that the resulting straight-line drawing is planar? It was known that this problem is NP-hard if the embedding can be chosen, but becomes polynomial for triangulated graphs of treewidth 3. We show here that in fact it can be answered for all planar graphs with a fixed combinatorial embedding that have constant treewidth and constant face-degree.

We explore the art gallery problem for the special case that the domain (gallery) P is an m-polyomino, a polyform whose cells are m unit squares. We study the combinatorics of guarding polyominoes in terms of the parameter m, in contrast with the traditional parameter n, the number of vertices of P; in particular, we show that floor((m+1)/3) point guards are always sufficient and sometimes necessary to cover an m-polyomino. When m d 3n/4 - 4, the point guard sufficiency condition yields a strictly lower guard number than floor(n/4), given by the art gallery theorem for orthogonal polygons. When pixels behave themselves like guards (pixel guards), we prove that floor(3m/11) + 1 guards are sufficient and sometimes necessary to cover an m-polyomino. We also study the algorithmic complexity of computing optimal guard sets for polyominoes. We prove that determining the guard number of a given m-polyomino is NP-hard. We provide polynomial-time algorithms to solve exactly some special cases in which the polyomino is "thin".

Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let $\poly$ be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside $\poly$. (A configuration specifies both a location and a direction of travel.) We present an O(n 2 log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.

International audience

In this paper, we study how to draw a planar partition, i.e., a planar graph with a given partition of the vertices.The goal is to obtain a drawing without crossings such that the partition is clearly visible.Previously, only the special case of bipartite graphs has been studied.Par two models of displaying the partition, we show necessary and sufficient conditions for the existence of a drawing, and how to test them in linear time.We also present linear-time algorithms to create such drawings, if possibIe.