Source author record

Timothy Johnson

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Taming the Knight's Tour: Minimizing Turns and Crossings

We introduce two new metrics of "simplicity" for knight's tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with $9.25n+O(1)$ turns and $12n+O(1)$ crossings on an $n\times n$ board, and we show lower bounds of $(6-ε)n$ and $4n-O(1)$ on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of $9.25/6+o(1)$ and $3+o(1)$ . Our algorithm takes linear time and is fully parallelizable, i.e., the tour can be computed in $O(n^2/p)$ time using $p$ processors in the CREW PRAM model. We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for $(1,4)$ -leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.

preprint2016arXiv

J-Viz: Sibling-First Recursive Graph Drawing for Visualizing Java Bytecode

We describe a graph visualization tool for visualizing Java bytecode. Our tool, which we call J-Viz, visualizes connected directed graphs according to a canonical node ordering, which we call the sibling-first recursive (SFR) numbering. The particular graphs we consider are derived from applying Shiver's k-CFA framework to Java bytecode, and our visualizer includes helpful links between the nodes of an input graph and the Java bytecode that produced it, as well as a decompiled version of that Java bytecode. We show through several case studies that the canonical drawing paradigm used in J-Viz is effective for identifying potential security vulnerabilities and repeated use of the same code in Java applications.

preprint2015arXiv

Knuthian Drawings of Series-Parallel Flowcharts

Inspired by a classic paper by Knuth, we revisit the problem of drawing flowcharts of loop-free algorithms, that is, degree-three series-parallel digraphs. Our drawing algorithms show that it is possible to produce Knuthian drawings of degree-three series-parallel digraphs with good aspect ratios and small numbers of edge bends.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.