research
∙
03/17/2023
The geodesic edge center of a simple polygon
The geodesic edge center of a polygon is a point c inside the polygon th...
share
research
∙
06/08/2022
Reconfiguration of Non-crossing Spanning Trees
For a set P of n points in the plane in general position, a non-crossing...
research
∙
06/06/2022
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...
research
∙
08/17/2021
Distant Representatives for Rectangles in the Plane
The input to the distant representatives problem is a set of n objects i...
research
∙
08/16/2021
The Visibility Center of a Simple Polygon
We introduce the visibility center of a set of points inside a polygon –...
research
∙
03/11/2021
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
research
∙
04/16/2020
Compatible Paths on Labelled Point Sets
Let P and Q be finite point sets of the same cardinality in ℝ^2, each la...
research
∙
04/13/2020
Reconstructing a Polyhedron between Polygons in Parallel Slices
Given two n-vertex polygons, P=(p_1, …, p_n) lying in the xy-plane at z=...
research
∙
03/03/2020
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 ...
research
∙
10/13/2019
Face flips in origami tessellations
Given a flat-foldable origami crease pattern G=(V,E) (a straight-line dr...
research
∙
05/02/2019
Minimum Ply Covering of Points with Disks and Squares
Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we ...
research
∙
05/01/2019
Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
research
∙
03/16/2019
Token Swapping on Trees
The input to the token swapping problem is a graph with vertices v_1, v_...
research
∙
01/06/2019
Maximum Matchings and Minimum Blocking Sets in Θ_6-Graphs
Θ_6-Graphs are important geometric graphs that have many applications es...
research
∙
08/29/2018
Recognition and Drawing of Stick Graphs
A Stick graph is an intersection graph of axis-aligned segments such tha...
research
∙
06/12/2018
Minimum Shared-Power Edge Cut
We introduce a problem called the Minimum Shared-Power Edge Cut (MSPEC)....
research
∙
02/19/2018
The Complexity of Drawing a Graph in a Polygonal Region
We prove that the following problem is complete for the existential theo...
research
∙
02/19/2018
Convexity-Increasing Morphs of Planar Graphs
We study the problem of convexifying drawings of planar graphs. Given an...
research
∙
01/25/2018
Rollercoasters and Caterpillars
A rollercoaster is a sequence of real numbers for which every maximal co...
research
∙
01/19/2018
Angle-Monotone Graphs: Construction and Local Routing
A geometric graph in the plane is angle-monotone of width γ if every pai...
research
∙
10/07/2017
A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
Given a triangulation of a point set in the plane, a flip deletes an edg...
research
∙
09/05/2017
Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges
Let T be an n-node tree of maximum degree 4, and let P be a set of n poi...
research
∙
07/01/2017
Angle-monotone Paths in Non-obtuse Triangulations
We reprove a result of Dehkordi, Frati, and Gudmundsson: every two verti...
research
∙
06/28/2017
