Search

There exist many variants of guarding an orthogonal polygon in an orthogonal fashion: sometimes a guard can see within a rectangle, along a staircase, or along an orthogonal path with at most k bends. In this paper, we study all these guarding models for the special case of orthogonal polygons that have bounded treewidth in some sense. As our main result, we show that the problem of finding the minimum number of guards in all these models becomes linear-time solvable on polygons with bounded treewidth. We complement our main result by giving some hardness results.

We consider the Minimum Dominating Set ( MDS ) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP -hard even when all the rectangles are “anchored” at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any ϵ > 0 , there exists a ( 2 + ϵ ) -approximation algorithm for the MDS problem on “diagonal-anchored” rectangles, providing the first O ( 1 ) -approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on “diagonal-anchored” rectangles is the same as the MDS problem on “diagonal-anchored” L -frames: the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a ( 2 + ϵ ) -approximation for the problem with “diagonal-anchored” L -frames. On the other hand, we show that the problem is APX -hard in case the input L -frames intersect the diagonal, or the horizontal segments of the L -frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L -frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called “edge intersection model” and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).

A 1-bend boundary labelling problem consists of an axis-aligned rectangle B, n points (called sites) in the interior, and n points (called ports) on the labels along the boundary of B. The goal is to find a set of n axis-aligned curves (called leaders), each having at most one bend and connecting one site to one port, such that the leaders are pairwise disjoint. A 1-bend boundary labelling problem is k-sided (\(1\le k\le 4\)) if the ports appear on k different sides of B. Kindermann et al. [Algorithmica, 76(1): 225–258, 2016] showed that the 1-bend 4-sided and 3-sided boundary labelling problems can be solved in \(O(n^9)\) and \(O(n^4)\) time, respectively. Bose et al. [SWAT, 12:1–12:14, 2018] improved the former running time to \(O(n^6)\) by reducing the problem to computing maximum independent set in an outerstring graph. In this paper, we improve both previous results by giving new algorithms with running times \(O(n^5)\) and \(O(n^3\log n)\) to solve the 1-bend 4-sided and 3-sided boundary labelling problems, respectively.

A graph $G$ with $n$ vertices is called an outerstring graph if it has an intersection representation of a set of $n$ curves inside a disk such that one endpoint of every curve is attached to the boundary of the disk. Given an outerstring graph representation, the Maximum Independent Set (MIS) problem of the underlying graph can be computed in $O(s^3)$ time, where $s$ is the number of segments in the representation (Keil et al., Comput. Geom., 60:19--25, 2017). If the strings are of constant size (e.g., line segments, L-shapes, etc.), then the algorithm takes $O(n^3)$ time. In this paper, we examine the fine-grained complexity of the MIS problem on some well-known outerstring representations. We show that solving the MIS problem on grounded segment and grounded square-L representations is at least as hard as solving MIS on circle graph representations. Note that no $O(n^{2-\delta})$-time algorithm, $\delta>0$, is known for the MIS problem on circle graphs. For the grounded string representations where the strings are $y$-monotone simple polygonal paths of constant length with segments at integral coordinates, we solve MIS in $O(n^2)$ time and show this to be the best possible under the strong exponential time hypothesis (SETH). For the intersection graph of $n$ L-shapes in the plane, we give a $(4\cdot \log OPT)$-approximation algorithm for MIS (where $OPT$ denotes the size of an optimal solution), improving the previously best-known $(4\cdot \log n)$-approximation algorithm of Biedl and Derka (WADS 2017)., Comment: A preliminary version of this paper appeared in the 16th International Symposium on Algorithms and Data Structures (WADS 2019)

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.

Let P be an orthogonal polygon with n vertices. A partition of P into rectangles is called conforming if it results from cutting P along a set of interior-disjoint line segments, each having both endpoints on the boundary of P. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any orthogonal line segment inside P. In this paper, we consider the problem of finding a conforming partition of P with minimum stabbing number. We first give an O ( n log ⁡ n ) -time algorithm to solve the problem when P is a histogram. For an arbitrary orthogonal polygon (even with holes), we give an integer programming formulation of the problem and show that a simple rounding results in a 2-approximation algorithm for the problem. Finally, we show that the problem is NP -hard if P is allowed to have holes.

A sliding camera in an orthogonal polygon P —that is, a polygon all of whose edges are axis-parallel—is a point guard g that travels back and forth along an axis-parallel line segment s inside P . A point p in P is guarded by g if and only if there exists a point q on s such that line segment pq is normal to s and contained in P . In the minimum sliding cameras (MSC) problem, the objective is to guard P with the minimum number of sliding cameras. We give a dynamic programming algorithm that solves the MSC problem exactly on monotone orthogonal polygons in O ( n ) time, improving the 2-approximation algorithm of Katz and Morgenstern (2011). More generally, our algorithm can be used to solve the MSC problem in O ( n ) time on simple orthogonal polygons P for which the dual graph induced by the vertical decomposition of P is a path. Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons.

A \emph{2-interval} is the union of two disjoint intervals on the real line. Two 2-intervals $D_1$ and $D_2$ are \emph{disjoint} if their intersection is empty (i.e., no interval of $D_1$ intersects any interval of $D_2$). There can be three different relations between two disjoint 2-intervals; namely, preceding ($, Comment: 11 pages, 6 figures

We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as follows. Given a set S of n geometric objects in the plane, we want to compute a maximum-size subset \(S'\subseteq S\) such that the intersection graph of the objects in \(S'\) is bipartite. We first show that the \(\texttt {MBS}\) problem is \(\texttt {NP}\)-hard on geometric graphs for which the maximum independent set is \(\texttt {NP}\)-hard (hence, it is \(\texttt {NP}\)-hard even on unit squares and unit disks). On the algorithmic side, we first give a simple \(\mathcal {O}(n)\)-time algorithm that solves the \(\texttt {MBS}\) problem on a set of n intervals. Then, we give an \(\mathcal {O}(n^2)\)-time algorithm that computes a near-optimal solution for the problem on circular-arc graphs. Moreover, for the approximability of the problem, we first present a \(\texttt {PTAS}\) for the problem on unit squares and unit disks. Then, we present efficient approximation algorithms with small-constant factors for the problem on unit squares, unit disks and unit-height rectangles. Finally, we study a closely related geometric problem, called Maximum Triangle-free Subgraph (\({{\texttt {\textit{MTFS}}}}\)), where the objective is the same as that of \(\texttt {MBS}\) except the intersection graph induced by the set \(S'\) needs to be triangle-free only (instead of being bipartite).

Consider a set $P$ of $n$ points on the boundary of an axis-aligned square $Q$. We study the boundary-anchored packing problem on $P$ in which the goal is to find a set of interior-disjoint axis-aligned rectangles in $Q$ such that each rectangle is anchored (has a corner at some point in $P$), each point in $P$ is used to anchor at most one rectangle, and the total area of the rectangles is maximized. Here, a rectangle is anchored at a point $p$ in $P$ if one of its corners coincides with $p$. In this paper, we show how to solve this problem in time linear in $n$, provided that the points of $P$ are given in sorted order along the boundary of $Q$. We also consider the problem for anchoring squares and give an $O(n^4)$-time algorithm when the points in $P$ lie on two opposite sides of $Q$., 18 pages, 11 figures

Consider $k$ robots initially located at a point inside a region $T$. Each robot can move anywhere in $T$ independently of other robots with maximum speed one. The goal of the robots is to \emph{evacuate} $T$ through an exit at an unknown location on the boundary of $T$. The objective is to minimize the \emph{evacuation time}, which is defined as the time the \emph{last} robot reaches the exit. We consider the \emph{face-to-face} communication model for the robots: a robot can communicate with another robot only when they meet in $T$. In this paper, we give upper and lower bounds for the face-to-face evacuation time by $k$ robots that are initially located at the centroid of a unit-sided equilateral triangle or square. For the case of a triangle with $k=2$ robots, we give a lower bound of $1+2/\sqrt{3} \approx 2.154$, and an algorithm with upper bound of 2.3367 on the worst-case evacuation time. We show that for any $k$, any algorithm for evacuating $k\geq 2$ robots requires at least $\sqrt{3}$ time. This bound is asymptotically optimal, as we show that even a straightforward strategy of evacuation by $k$ robots gives an upper bound of $\sqrt{3} + 3/k$. For $k=3$ and $4$, we give better algorithms with evacuation times of 2.0887 and 1.9816, respectively. For the case of the square and $k=2$, we give an algorithm with evacuation time of $3.4645$ and show that any algorithm requires time at least $3.118$ to evacuate in the worst-case. Moreover, for $k=3$, and $4$, we give algorithms with evacuation times 3.1786 and 2.6646, respectively. The algorithms given for $k=3$ and $4$ for evacuation in the triangle or the square can be easily generalized for larger values of $k$., 28 pages, 14 figures

A graph G with n vertices is called an outerstring graph if it has an intersection representation of a set of n curves inside a disk such that one endpoint of every curve is attached to the boundary of the disk. Given an outerstring graph representation, the Maximum Independent Set (\(\mathsf {MIS}\)) problem of the underlying graph can be solved in \(O(s^3)\) time, where s is the number of segments in the representation (Keil et al., Comput. Geom., 60:19–25, 2017). If the strings are of constant size (e.g., line segments, \(\mathsf {L}\)-shapes, etc.), then the algorithm takes \(O(n^3)\) time.

Let $P$ be a polygon with $r>0$ reflex vertices and possibly with holes and islands. A subsuming polygon of $P$ is a polygon $P'$ such that $P \subseteq P'$, each connected component $R$ of $P$ is a subset of a distinct connected component $R'$ of $P'$, and the reflex corners of $R$ coincide with those of $R'$. A subsuming chain of $P'$ is a minimal path on the boundary of $P'$ whose two end edges coincide with two edges of $P$. Aichholzer et al. proved that every polygon $P$ has a subsuming polygon with $O(r)$ vertices, and posed an open problem to determine the computational complexity of computing subsuming polygons with the minimum number of convex vertices. We prove that the problem of computing an optimal subsuming polygon is NP-complete, but the complexity remains open for simple polygons (i.e., polygons without holes). Our NP-hardness result holds even when the subsuming chains are restricted to have constant length and lie on the arrangement of lines determined by the edges of the input polygon. We show that this restriction makes the problem polynomial-time solvable for simple polygons., 15 pages, 9 figures

In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be \(\mathsf {NP}\)-hard, even if the line segments in S are axis-parallel, and it remains \(\mathsf {NP}\)-hard when the goal is cover the “rectangular” cells (i.e., cells that are defined by exactly four axis-parallel line segments).

In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set $S$ of $n$ line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment $s$ covers a cell $f$ if $s$ is incident to $f$. The problem was shown to be NP-hard, even if the line segments in $S$ are axis-parallel, and it remains NP-hard when the goal is cover the "rectangular" cells (i.e., cells that are defined by exactly four axis-parallel line segments). In this paper, we consider the approximability of the problem. We first give a PTAS for the problem when the line segments in $S$ are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is APX-hard. We also consider the parameterized complexity of the problem and prove that the problem is FPT when parameterized by the size of an optimal solution. Our FPT algorithm works when the line segments in $S$ have two orientations and the goal is to cover all cells, complementing that of Korman et al. in which the goal is to cover the "rectangular" cells., Comment: 12 pages, 4 figures. To appear in COCOA 2018

In this paper, we study grid-obstacle representations of graphs where we assign grid-points to vertices and define obstacles such that an edge exists if and only if an xy-monotone grid path connects the two endpoints without hitting an obstacle or another vertex. It was previously argued that all planar graphs have a grid-obstacle representation in 2D, and all graphs have a grid-obstacle representation in 3D. In this paper, we show that such constructions are possible with significantly smaller grid-size than previously achieved. Then we study the variant where vertices are not blocking, and show that then grid-obstacle representations exist for bipartite graphs. The latter has applications in so-called staircase guarding of orthogonal polygons; using our grid-obstacle representations, we show that staircase guarding is NP-hard in 2D.

A graph G is called \({B}_k\)-EPG (resp., \({B}_k\)-VPG), for some constant \(k\ge 0\), if it has a string representation on an axis-parallel grid such that each vertex is a path with at most k bends and two vertices are adjacent in G if and only if the corresponding strings share at least one grid edge (resp., the corresponding strings intersect each other). If two adjacent strings of a B\(_k\)-VPG graph intersect each other exactly once, then the graph is called a one-string B\(_k\)-VPG graph.

Let P be an orthogonal polygon with n vertices. A sliding camera travels back and forth along an orthogonal line segment s ⊆ P corresponding to its trajectory. The camera sees a point p ∈ P if there is a point q ∈ s such that p q ‾ is a line segment normal to s that is completely contained in P. In the Minimum-Cardinality Sliding Cameras (MCSC) problem, the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i.e., every point in P can be seen by some sliding camera in S), while in the Minimum-Length Sliding Cameras (MLSC) problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel. In this paper, we answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP -complete when P is allowed to have holes, and (iii) an O ( n 3 log ⁡ n ) -time 2-approximation algorithm for the MCSC problem on [NE]-star-shaped orthogonal polygons with n vertices (similarly, [NW]-, [SE]-, or [SW]-star-shaped orthogonal polygons).

Motivated by comparative genomics, Chen et al. [9] introduced the Maximum Duo-preservation String Mapping (MDSM) problem in which we are given two strings \(s_1\) and \(s_2\) from the same alphabet and the goal is to find a mapping \(\pi \) between them so as to maximize the number of duos preserved. A duo is any two consecutive characters in a string and it is preserved in the mapping if its two consecutive characters in \(s_1\) are mapped to same two consecutive characters in \(s_2\). The MDSM problem is known to be NP-hard and there are approximation algorithms for this problem [3, 5], all of which consider only the “unweighted” version of the problem in the sense that a duo from \(s_1\) is preserved by mapping to any same duo in \(s_2\) regardless of their positions in the respective strings. However, it is well-desired in comparative genomics to find mappings that consider preserving duos that are “closer” to each other under some distance measure [18].

A sliding camera inside an orthogonal polygon P is a point guard that travels back and forth along an orthogonal line segment \(\gamma \) in P. The sliding camera g can see a point p in P if the perpendicular from p onto \(\gamma \) is inside P. In this paper, we give the first constant-factor approximation algorithm for the problem of guarding P with the minimum number of sliding cameras. Next, we show that the sliding guards problem is linear-time solvable if the (suitably defined) dual graph of the polygon has bounded treewidth. On the other hand, we show that the problem is NP-hard on orthogonal polygons with holes even if only horizontal cameras are allowed. Finally, we study art gallery theorems for sliding cameras, thus, give upper and lower bounds in terms of the number of sliding cameras needed relative to the number of vertices n.

A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles. The relationships between 1-planar graphs and RAC drawings have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC drawable and graphs that have a straight-line RAC drawing but that are not 1-planar. Also, straight-line RAC drawings always exist for IC-planar graphs, a subclass of 1-planar graphs. One of the main questions still open is whether every 1-planar graph has a RAC drawing with at most one bend per edge. We positively answer this question., Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

Let P be a polygon with \(r>0\) reflex vertices and possibly with holes. A subsuming polygon of P is a polygon \(P'\) such that \(P \subseteq P'\), each connected component \(R'\) of \(P'\) subsumes a distinct component R of P, i.e., \(R\subseteq R'\), and the reflex corners of R coincide with the reflex corners of \(R'\). A subsuming chain of \(P'\) is a minimal path on the boundary of \(P'\) whose two end edges coincide with two edges of P. Aichholzer et al. proved that every polygon P has a subsuming polygon with O(r) vertices. Let \(\mathcal {A}_e(P)\) (resp., \(\mathcal {A}_v(P)\)) be the arrangement of lines determined by the edges (resp., pairs of vertices) of P. Aichholzer et al. observed that a challenge of computing an optimal subsuming polygon \(P'_{min}\), i.e., a subsuming polygon with minimum number of convex vertices, is that it may not always lie on \(\mathcal {A}_e(P)\). We prove that in some settings, one can find an optimal subsuming polygon for a given simple polygon in polynomial time, i.e., when \(\mathcal {A}_e(P'_{min}) = \mathcal {A}_e(P)\) and the subsuming chains are of constant length. In contrast, we prove the problem to be NP-hard for polygons with holes, even if there exists some \(P'_{min}\) with \(\mathcal {A}_e(P'_{min}) = \mathcal {A}_e(P)\) and subsuming chains are of length three. Both results extend to the scenario when \(\mathcal {A}_v(P'_{min}) = \mathcal {A}_v(P)\).

A strict orthogonal drawing of a graph G = (V, E) in ℝ2 is a drawing of G such that each vertex is mapped to a distinct point and each edge is mapped to a horizontal or vertical line segment. A graph G is HV-restricted if each of its edges is assigned a horizontal or vertical orientation. A strict orthogonal drawing of an HV-restricted graph G is good if it is planar and respects the edge orientations of G. In this paper we give a polynomial-time algorithm to check whether a given HV-restricted plane graph (i.e., a planar graph with a fixed combinatorial embedding) admits a good orthogonal drawing preserving the input embedding, which settles an open question posed by Maňuch, Patterson, Poon and Thachuk (GD 2010). We then examine HV-restricted planar graphs (i.e., when the embedding is not fixed). Here we completely characterize the 2-connected maximum-degree-three HV-restricted outerplanar graphs that admit good orthogonal drawings.

Consider a sliding camera that travels back and forth along an orthogonal line segment s inside an orthogonal polygon P with n vertices. The camera can see a point p inside P if and only if there exists a line segment containing p that crosses s at a right angle and is completely contained in P. In the minimum sliding cameras (MSC) problem, the objective is to guard P with the minimum number of sliding cameras. In this paper, we give an O(n 5/2)-time (7/2)-approximation algorithm to the MSC problem on any simple orthogonal polygon with n vertices, answering a question posed by Katz and Morgenstern (2011). To the best of our knowledge, this is the first constant-factor approximation algorithm for this problem.