Contact Information

Computer Science Department
Colgate University
McGregory Hall, 3rd Floor
13 Oak Drive
Hamilton, NY 13346
(tel) 315.228.7719
Charlotte Jablonski, Administrative Assistant
cjablonski@colgate.edu

Event Detail

Dept Tea: Reconstructing Generalized Staircase Polygons with Uniform Step Length

Start: Tuesday, September 19, 2017, 11:30 a.m.
End: Tuesday, September 19, 2017, 12:20 p.m.
Location: 319 McGregory Hall

Speaker: Prof. Darren Strash

Abstract: In this talk, I will discuss my recent research on visibility graph reconstruction: the problem of constructing a polygon that has a given visibility graph. This is a fundamental problem with unknown complexity, although visibility graph recognition (the problem of recognizing if a graph is a visibility graph of some polygon) is known to be in PSPACE.

I show that two classes of uniform step length polygons can be reconstructed efficiently by finding and removing rectangles formed between consecutive convex boundary vertices, called tabs. This technique gives a O(n^2m)-time reconstruction algorithm for orthogonally convex polygons, where n and m are the number of vertices and edges in the visibility graph, respectively. I also show that reconstructing a monotone chain of staircases (called a histogram) is fixed-parameter tractable, when parameterized on the number of tabs, and polynomially solvable in time O(n^2m) under reasonable alignment restrictions.

This is joint work with Nodari Sitchinava; to be presented at the 25th Symposium on Graph Drawing and Network Visualization.