I am a third 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 dot edu
Office: DBH 4219
We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known to be NP-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains NP-complete for graphs of bounded bandwidth, pathwidth, or treewidth.
Joint work with David Eppstein and Sergio Cabello.
To be presented at WADS 2013. Preprint on arXiv.
We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguous subintervals of these timestamps. We provide data structures for these problems that use near-linear preprocessing time, linear space, and sublogarithmic query time to handle queries that ask for the number of connected components, number of components that contain cycles, number of vertices whose degree equals or is at most some predetermined value, number of vertices that can be reached from a starting set of vertices by time-increasing paths, and related queries.
Joint work with Christopher DuBois, David Eppstein and Padhraic Smyth.
To be presented at SODA 2013. Poster presented at NIPS Workshop 2012. Preprint on arXiv.
We present techniques for using social gravity as an additional force in force-directed layouts, together with a scaling technique, to produce drawings of trees and forests, as well as more complex social networks. Social gravity assigns mass to vertices in proportion to their network centrality, which allows vertices that are more graph-theoretically central to be visualized in physically central locations. Scaling varies the gravitational force throughout the simulation, and reduces crossings relative to unscaled gravity.
Joint work with David Eppstein, Michael T. Goodrich and Lowell Trott.
Presented at Graph Drawing 2012. Preprint on arXiv.
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. Full version in the GD 2011 Special Issue of JGAA. 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.
Over the years I have created this LaTeX template for homework submissions.