BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Anna Lubiw

Anna Lubiw contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryData Structures and AlgorithmsComputational ComplexityDiscrete Mathematicsmath.COmath.MGRobotics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

Forbidding Edges between Points in the Plane to Disconnect the Triangulation Flip Graph

The flip graph for a set $P$ of points in the plane has a vertex for every triangulation of $P$, and an edge when two triangulations differ by one flip that replaces one triangulation edge by another. The flip graph is known to have some connectivity properties: (1) the flip graph is connected; (2) connectivity still holds when restricted to triangulations containing some constrained edges between the points; (3) for $P$ in general position of size $n$, the flip graph is $\lceil \frac{n}{2} -2 \rceil$-connected, a recent result of Wagner and Welzl (SODA 2020). We introduce the study of connectivity properties of the flip graph when some edges between points are forbidden. An edge $e$ between two points is a flip cut edge if eliminating triangulations containing $e$ results in a disconnected flip graph. More generally, a set $X$ of edges between points of $P$ is a flip cut set if eliminating all triangulations that contain edges of $X$ results in a disconnected flip graph. The flip cut number of $P$ is the minimum size of a flip cut set. We give a characterization of flip cut edges that leads to an $O(n \log n)$ time algorithm to test if an edge is a flip cut edge and, with that as preprocessing, an $O(n)$ time algorithm to test if two triangulations are in the same connected component of the flip graph. For a set of $n$ points in convex position (whose flip graph is the 1-skeleton of the associahedron) we prove that the flip cut number is $n-3$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Hardness of Token Swapping on Trees

Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to use the shortest possible sequence of swaps, each of which exchanges the tokens at the two endpoints of an edge of the graph. In parallel token swapping, the goal is to use the fewest rounds, each of which consists of one or more swaps on the edges of a matching. We prove that both of these problems remain NP-hard when the graph is restricted to be a tree. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robot motion planning, game theory, and engineering. Previous work establishes NP-completeness on general graphs (for both problems); polynomial-time algorithms for simple graph classes such as cliques, stars, paths, and cycles; and constant-factor approximation algorithms in some cases. The two natural cases of sequential and parallel token swapping in trees were first studied over thirty years ago (as "sorting with a transposition tree") and over twenty-five years ago (as "routing permutations via matchings"), yet their complexities were previously unknown. We also show limitations on approximation of sequential token swapping on trees: we identify a broad class of algorithms that encompass all three known polynomial-time algorithms that achieve the best known approximation factor (which is $2$) and show that no such algorithm can achieve an approximation factor less than $2$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reconfiguration of Non-crossing Spanning Trees

For a set $P$ of $n$ points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. We study the problem of reconfiguring one non-crossing spanning tree of $P$ to another using a sequence of flips where each flip removes one edge and adds one new edge so that the result is again a non-crossing spanning tree of $P$. There is a known upper bound of $2n-4$ flips [Avis and Fukuda, 1996] and a lower bound of $1.5n - 5$ flips. We give a reconfiguration algorithm that uses at most $2n-3$ flips but reduces that to $1.5n-2$ flips when one tree is a path and either: the points are in convex position; or the path is monotone in some direction. For points in convex position, we prove an upper bound of $2d - Ω(\log d)$ where $d$ is half the size of the symmetric difference between the trees. We also examine whether the happy edges (those common to the initial and final trees) need to flip, and we find exact minimum flip distances for small point sets using exhaustive search.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Building a larger class of graphs for efficient reconfiguration of vertex colouring

A $k$-colouring of a graph $G$ is an assignment of at most $k$ colours to the vertices of $G$ so that adjacent vertices are assigned different colours. The reconfiguration graph of the $k$-colourings, $\mathcal{R}_k(G)$, is the graph whose vertices are the $k$-colourings of $G$ and two colourings are joined by an edge in $\mathcal{R}_k(G)$ if they differ in colour on exactly one vertex. For a $k$-colourable graph $G$, we investigate the connectivity and diameter of $\mathcal{R}_{k+1}(G)$. It is known that not all weakly chordal graphs have the property that $\mathcal{R}_{k+1}(G)$ is connected. On the other hand, $\mathcal{R}_{k+1}(G)$ is connected and of diameter $O(n^2)$ for several subclasses of weakly chordal graphs such as chordal, chordal bipartite, and $P_4$-free graphs. We introduce a new class of graphs called OAT graphs that extends the latter classes and in fact extends outside the class of weakly chordal graphs. OAT graphs are built from four simple operations, disjoint union, join, and the addition of a clique or comparable vertex. We prove that if $G$ is a $k$-colourable OAT graph then $\mathcal{R}_{k+1}(G)$ is connected with diameter $O(n^2)$. Furthermore, we give polynomial time algorithms to recognize OAT graphs and to find a path between any two colourings in $\mathcal{R}_{k+1}(G)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Compatible Paths on Labelled Point Sets

Let $P$ and $Q$ be finite point sets of the same cardinality in $\mathbb{R}^2$, each labelled from $1$ to $n$. Two noncrossing geometric graphs $G_P$ and $G_Q$ spanning $P$ and $Q$, respectively, are called compatible if for every face $f$ in $G_P$, there exists a corresponding face in $G_Q$ with the same clockwise ordering of the vertices on its boundary as in $f$. In particular, $G_P$ and $G_Q$ must be straight-line embeddings of the same connected $n$-vertex graph. Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: $O(n)$ time for points in convex position; $O(n^2)$ time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and $O(n^2 \log n)$ time for points in general position if the paths are restricted to be monotone.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reconstructing a Polyhedron between Polygons in Parallel Slices

Given two $n$-vertex polygons, $P=(p_1, \ldots, p_n)$ lying in the $xy$-plane at $z=0$, and $P'=(p'_1, \ldots, p'_n)$ lying in the $xy$-plane at $z=1$, a banded surface is a triangulated surface homeomorphic to an annulus connecting $P$ and $P'$ such that the triangulation's edge set contains vertex disjoint paths $π_i$ connecting $p_i$ to $p'_i$ for all $i =1, \ldots, n$. The surface then consists of bands, where the $i$th band goes between $π_i$ and $π_{i+1}$. We give a polynomial-time algorithm to find a banded surface without Steiner points if one exists. We explore connections between banded surfaces and linear morphs, where time in the morph corresponds to the $z$ direction. In particular, we show that if $P$ and $P'$ are convex and the linear morph from $P$ to $P'$ (which moves the $i$th vertex on a straight line from $p_i$ to $p'_i$) remains planar at all times, then there is a banded surface without Steiner points.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron

We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid--for example, the surface of any polycube. The folding is efficient: for target surfaces topologically equivalent to a sphere, the strip needs to have only twice the target surface area, and the folding stacks at most two layers of material anywhere. These geometric results offer a new way to build programmable matter that is substantially more efficient than what is possible with a square $N \times N$ sheet of material, which can fold into all polycubes only of surface area $O(N)$ and may stack $Θ(N^2)$ layers at one point. We also show how our strip foldings can be executed by a rigid motion without collisions (albeit assuming zero thickness), which is not possible in general with 2D sheet folding. To achieve these results, we develop new approximation algorithms for milling the surface of a grid polyhedron, which simultaneously give a 2-approximation in tour length and an 8/3-approximation in the number of turns. Both length and turns consume area when folding a strip, so we build on past approximation algorithms for these two objectives from 2D milling.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Face flips in origami tessellations

Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $μ:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $F$ of $G$ to create a new MV assignment $μ_F$ which equals $μ$ except for all creases $e$ bordering $F$, where we have $μ_F(e)=-μ(e)$. In this paper we explore the configuration space of face flips for a variety of crease patterns $G$ that are tilings of the plane, proving examples where $μ_F$ results in a MV assignment that is either never, sometimes, or always flat-foldable for various choices of $F$. We also consider the problem of finding, given two foldable MV assignments $μ_1$ and $μ_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $μ_1$ into $μ_2$. We find polynomial-time algorithms for this in the cases where $G$ is either a square grid or the Miura-ori, and show that this problem is NP-hard in the case where $G$ is the triangle lattice.

0 citations0 reviewsNo code linkedOpen access