research
∙
07/20/2023
Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs
We study methods to manipulate weights in stress-graph embeddings to imp...
share
research
∙
06/22/2023
Geometric Graphs with Unbounded Flip-Width
We consider the flip-width of geometric graphs, a notion of graph width ...
research
∙
06/20/2023
A Parameterized Algorithm for Flat Folding
We prove that testing the flat foldability of an origami crease pattern ...
research
∙
06/19/2023
Quasipolynomiality of the Smallest Missing Induced Subgraph
We study the problem of finding the smallest graph that does not occur a...
research
∙
05/16/2023
Lower Bounds for Non-Adaptive Shortest Path Relaxation
We consider single-source shortest path algorithms that perform a sequen...
research
∙
03/29/2023
On the complexity of embedding in graph products
Graph embedding, especially as a subgraph of a grid, is an old topic in ...
research
∙
03/01/2023
Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
We show that, for planar point sets, the number of non-crossing Hamilton...
research
∙
07/20/2022
Improved mixing for the convex polygon triangulation flip walk
We prove that the well-studied triangulation flip walk on a convex point...
research
∙
06/26/2022
Locked and unlocked smooth embeddings of surfaces
We study the continuous motion of smooth isometric embeddings of a plana...
research
∙
06/22/2022
Reflections in an octagonal mirror maze
Suppose we are given an environment consisting of axis-parallel and diag...
research
∙
06/21/2022
Orthogonal dissection into few rectangles
We describe a polynomial time algorithm that takes as input a polygon wi...
research
∙
03/24/2022
Geometric Dominating Sets
We consider a minimizing variant of the well-known No-Three-In-Line Prob...
research
∙
02/10/2022
Three-dimensional graph products with unbounded stack-number
We prove that the stack-number of the strong product of three n-vertex p...
research
∙
12/22/2021
The Complexity of Iterated Reversible Computation
We define a complexity class 𝖨𝖡 as the class of functional problems redu...
research
∙
11/06/2021
Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs
We give a new rapid mixing result for a natural random walk on the indep...
research
∙
10/12/2021
Finding Relevant Points for Nearest-Neighbor Classification
In nearest-neighbor classification problems, a set of d-dimensional trai...
research
∙
08/17/2021
Limitations on Realistic Hyperbolic Graph Drawing
We show that several types of graph drawing in the hyperbolic plane requ...
research
∙
07/08/2021
Angles of Arc-Polygons and Lombardi Drawings of Cacti
We characterize the triples of interior angles that are possible in non-...
research
∙
06/29/2021
Optimal Spanners for Unit Ball Graphs in Doubling Metrics
Resolving an open question from 2006, we prove the existence of light-we...
research
∙
05/11/2021
A Stronger Lower Bound on Parametric Minimum Spanning Trees
We prove that, for an undirected graph with n vertices and m edges, each...
research
∙
01/25/2021
Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes
We investigate the parameterized complexity of finding subgraphs with he...
research
∙
11/09/2020
Stack-number is not bounded by queue-number
We describe a family of graphs with queue-number at most 4 but unbounded...
research
∙
10/19/2020
The Graphs of Stably Matchable Pairs
We study the graphs formed from instances of the stable matching problem...
research
∙
08/31/2020
On Polyhedral Realization with Isosceles Triangles
Answering a question posed by Joseph Malkevitch, we prove that there exi...
research
∙
07/31/2020
New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
research
∙
07/28/2020
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra
We present new examples of topologically convex edge-ununfoldable polyhe...
research
∙
07/16/2020
Dynamic Products of Ranks
We describe a data structure that can maintain a dynamic set of points g...
research
∙
05/01/2020
On the treewidth of Hanoi graphs
The objective of the well-known Towers of Hanoi puzzle is to move a set ...
research
∙
04/17/2020
Low-stretch spanning trees of graphs with bounded width
We study the problem of low-stretch spanning trees in graphs of bounded ...
research
∙
02/14/2020
On the Edge Crossings of the Greedy Spanner
t-spanners are used to approximate the pairwise distances between a set ...
research
∙
02/05/2020
Simplifying Activity-on-Edge Graphs
We formalize the simplification of activity-on-edge graphs used for visu...
research
∙
10/13/2019
Face flips in origami tessellations
Given a flat-foldable origami crease pattern G=(V,E) (a straight-line dr...
research
∙
10/04/2019
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width
For a clustered graph, i.e, a graph whose vertex set is recursively part...
research
∙
08/21/2019
Existence and hardness of conveyor belts
An open problem of Manuel Abellanas asks whether every set of disjoint c...
research
∙
08/15/2019
Homotopy height, grid-major height and graph-drawing height
It is well-known that both the pathwidth and the outer-planarity of a gr...
research
∙
08/15/2019
Tracking Paths in Planar Graphs
We consider the NP-complete problem of tracking paths in a graph, first ...
research
∙
06/11/2019
Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings
We find a family of planar bipartite graphs all of whose Lombardi drawin...
research
∙
05/01/2019
Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
research
∙
03/12/2019
Cubic Planar Graphs that cannot be Drawn on few Lines
For every integer ℓ, we construct a cubic 3-vertex-connected planar bipa...
research
∙
03/12/2019
Counting Polygon Triangulations is Hard
We prove that it is #P-complete to count the triangulations of a (non-si...
research
∙
02/19/2019
Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains
We show new applications of the nearest-neighbor chain algorithm, a tech...
research
∙
10/19/2018
Minor-closed graph classes with bounded layered pathwidth
We prove that a minor-closed class of graphs has bounded layered pathwid...
research
∙
10/17/2018
Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
We consider decomposing a 3-connected planar graph G using laminar separ...
research
∙
10/04/2018
Parameterized Leaf Power Recognition via Embedding into Graph Products
The k-leaf power graph G of a tree T is a graph whose vertices are the l...
research
∙
08/17/2018
Realization and Connectivity of the Graphs of Origami Flat Foldings
We investigate the graphs formed from the vertices and creases of an ori...
research
∙
08/07/2018
The Parameterized Complexity of Finding Point Sets with Hereditary Properties
We consider problems where the input is a set of points in the plane and...
research
∙
08/01/2018
Geometric Fingerprint Recognition via Oriented Point-Set Pattern Matching
Motivated by the problem of fingerprint matching, we present geometric a...
research
∙
05/14/2018
Quadratic Time Algorithms Appear to be Optimal for Sorting Evolving Data
We empirically study sorting in the evolving data model. In this model, ...
research
∙
05/10/2018
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
We consider the computational complexity of reconfiguration problems, in...
research
∙
05/09/2018
