Arrow Research search

Author name cluster

Anna Lubiw

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

TCS Journal 2020 Journal Article

On compatible triangulations with a minimum number of Steiner points

  • Anna Lubiw
  • Debajyoti Mondal

Two vertex-labelled polygons are compatible if they have the same clockwise cyclic ordering of vertices. The definition extends to polygonal regions (polygons with holes) and to triangulations—for every face, the clockwise cyclic order of vertices on the boundary must be the same. It is known that every pair of compatible n-vertex polygonal regions can be extended to compatible triangulations by adding O ( n 2 ) Steiner points. Furthermore, Ω ( n 2 ) Steiner points are sometimes necessary, even for a pair of polygons. Compatible triangulations provide piecewise linear homeomorphisms and are also a crucial first step in morphing planar graph drawings, aka “2D shape animation. ” An intriguing open question, first posed by Aronov, Seidel, and Souvaine in 1993, is to decide if two compatible polygons have compatible triangulations with at most k Steiner points. In this paper we prove the problem to be NP-hard for polygons with holes. The question remains open for simple polygons.

Details DOI

TCS Journal 2019 Journal Article

Recognition and drawing of stick graphs

  • Felice De Luca
  • Md Iqbal Hossain
  • Stephen Kobourov
  • Anna Lubiw
  • Debajyoti Mondal

A Stick graph is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a “ground line, ” a line with slope −1. It is an open question to decide in polynomial time whether a given bipartite graph G with bipartition A ∪ B has a Stick representation where the vertices in A and B correspond to horizontal and vertical segments, respectively. We prove that G has a Stick representation if and only if there are orderings of A and B such that G's bipartite adjacency matrix with rows A and columns B excludes three small ‘forbidden’ submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of A and B permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of A is given, or neither ordering is given, we present some partial results about graphs that are, or are not, Stick representable.

Details DOI

SODA Conference 2013 Conference Paper

Morphing Planar Graph Drawings with a Polynomial Number of Steps

  • Soroush Alamdari
  • Patrizio Angelini
  • Timothy M. Chan
  • Giuseppe Di Battista
  • Fabrizio Frati
  • Anna Lubiw
  • Maurizio Patrignani
  • Vincenzo Roselli

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i. e. , a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O ( n 2 ) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O ( n 4 ) steps.

Details

MFCS Conference 2004 Conference Paper

Angles and Lengths in Reconfigurations of Polygons and Polyhedra

  • Therese C. Biedl
  • Anna Lubiw
  • Michael J. Spriggs

Abstract We explore the possibility of reconfiguring, or “morphing”, one simple polygon to another, maintaining simplicity, and preserving some properties of angles and edge lengths. In linkage reconfiguration, edge lengths must be preserved. By contrast, a monotone morph preserves edge directions and changes edge lengths monotonically. A monotone morph is only possible for parallel polygons—ones with corresponding edges parallel. Our main results are that monotone morphs exist for parallel pairs of polygons that are: (1) convex; or (2) orthogonally convex. Our morphs either move vertices in straight lines, or change few edge lengths at once. On the negative side, we show that it is NP-hard to decide if two simple parallel orthogonal polygons have a monotone morph. We also establish which of these results extend to 3-dimensional polyhedra.

Details

STOC Conference 2003 Conference Paper

Touring a sequence of polygons

  • Moshe Dror
  • Alon Efrat
  • Anna Lubiw
  • Joseph S. B. Mitchell

Given a sequence of k polygons in the plane, a start point s , and a target point, t , we seek a shortest path that starts at s , visits in order each of the polygons, and ends at t . If the polygons are disjoint and convex, we give an algorithm running in time O(kn log (n/k)) , where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk 2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m) , where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons" problem is NP-hard.The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n 2 log n) time and the watchman route problem (through a fixed point s ) in time O(n 3 log n) , compared with the previous time bounds of O(n 3 ) and O(n 4 ) , respectively.

Details

TCS Journal 2002 Journal Article

Embedding problems for paths with direction constrained edges

  • Giuseppe Di Battista
  • Giuseppe Liotta
  • Anna Lubiw
  • Sue Whitesides

We determine the reachability properties of the embeddings in R3 of a directed path, in the graph-theoretic sense, whose edges have each been assigned a desired direction (East, West, North, South, Up, or Down) but no length. We ask which points of R3 can be reached by the terminus of an embedding of such a path, by choosing appropriate positive lengths for the edges, if the embedded path starts at the origin, does not intersect itself, and respects the directions pre-assigned to its edges. This problem arises in the context of extending planar graph embedding techniques and VLSI rectilinear layout techniques from 2D to 3D. We give a combinatorial characterization of reachability that yields linear time recognition and layout algorithms. Finally, we extend our characterization to Rd, d>3.

Details DOI