# Michael J. Bannister

## Research

#### Small Superpatterns for Dominance Drawing

We exploit the connection between dominance drawings of directed acyclic graphs and permutations, in both directions, to provide improved bounds on the size of universal point sets for certain types of dominance drawing and on superpatterns for certain natural classes of permutations. In particular we show that there exist universal point sets for dominance drawings of the Hasse diagrams of width-two partial orders of size $O(n^{3/2})$, universal point sets for dominance drawings of $st$-outerplanar graphs of size $O(n\log n)$, and universal point sets for dominance drawings of directed trees of size $O(n)$. We show that $321$-avoiding permutations have superpatterns of size $O(n^{3/2})$, riffle permutations ($321$-, $2143$-, and $2413$-avoiding permutations) have superpatterns of size $O(n)$, and the concatenations of sequences of riffles and their inverses have superpatterns of size $O(n\log n)$. Our analysis includes a calculation of the leading constants in these bounds.

Joint work with William E. Devanny and David Eppstein.
To be presented at ANALCO 2014. Preprint on arXiv.

#### Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

We investigate exact crossing minimization for graphs that differ from trees by a small number of additional edges, for several variants of the crossing minimization problem. In particular, we provide fixed parameter tractable algorithms for the $1$-page book crossing number, the $2$-page book crossing number, and the minimum number of crossed edges in $1$-page and $2$-page book drawings.

Joint work with David Eppstein and Joe Simons.
Presented at Graph Drawing 2013. Preprint on arXiv.

#### Superpatterns and Universal Point Sets

An old open problem in graph drawing asks for the size of a universal point set, a set of points that can be used as vertices for straight-line drawings of all $n$-vertex planar graphs. We connect this problem to the theory of permutation patterns, where another open problem concerns the size of superpatterns, a permutation that contains all patterns of a given size. We extend this definition to superpatterns for classes of permutations determined by forbidden patterns, and we construct superpatterns for the $213$-avoiding permutations of size $n^2/4+\Theta(n)$, half the size of the best known superpatterns for unconstrained permutations. We use these superpatterns to construct universal point sets of size $n^2/4-\Theta(n)$, half the size of the previous upper bound. We prove that every proper subclass of the $213$-avoiding permutations has superpatterns of size $O(n\log^{O(1)}n)$, and we use this bound to prove that the planar graphs of bounded pathwidth have near-linear universal point sets.

Joint work with Zhanpeng Cheng, William E. Devanny and David Eppstein.
Presented at Graph Drawing 2013. Preprint on arXiv.

#### Parameterized Complexity of 1-Planarity

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 Sergio Cabello and David Eppstein.
Presented at WADS 2013. Preprint on arXiv.

#### Windows into Relational Events

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.
Presented at SODA 2013. Poster presented at NIPS Workshop 2012. Preprint on arXiv.

#### Force-Directed Graph Drawing Using Social Gravity and Scaling

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.

#### Randomized Speedup of the Bellman–Ford Algorithm

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.

#### Inapproximability of Orthogonal Compaction

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.

## Miscellaneous

#### $\LaTeX$ Homework Template

Over the years I have created this LaTeX template for homework submissions.