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

**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.