I am a second year Ph.D. student in the Computer Science department at the University of California, Irvine. I am advised by David Eppstein in the Center for Algorithms and Theory of Computation. My research interest are in the design and analysis of algorithms, particularly geometric and graph algorithms.
Email: mbannist at uci
Office: DBH 4219
We show that by first randomizing the vertices in a directed graph a $2/3$ improvement is had over Yen's improvement of the Bellman-Ford algorithm. This improves the runtime to less than $mn/3 + m$ in the sparse case and $n^3/6$ in the dense case in expectation, and less than $mn/3 + o(mn)$ and $n^3/6 + o(n^3)$ with high probability. The high probability bounds lead to a speed up in negative cycle detection in the sparse case.
Joint work with David Eppstein. Presented at ANALCO 2012. Preprint on arXiv.
We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated to within better than a polynomial factor in polynomial time unless its the case that $\mathsf{P} = \mathsf{NP}$. We also provide a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a small number of rows.
Joint work with David Eppstein and Joe Simons. Presented at Graph Drawing 2011.
To appear in the special issue of JGAA for GD 2011. Preprint on arXiv.
The Ipe extensible drawing editor is drawing tool for producing pdf images to be included in LaTeX documents, created by Otfried Cheong. I have compiled a OS X application bundle for use on my laptop. I make no guarantees that this program will work on your computer! Also, this version may be out of date.