cscheid.net
some papers, some blog posts, some code. like nowhere else on the web.
Drawing Large Graphs by Low-Rank Stress Majorization
Marc Khoury, Yifan Hu, Shankar Krishnan, Carlos Scheidegger. Eurovis 2012, to appear.
Optimizing a stress model is a natural technique for drawing graphs: one seeks an embedding into $R^d$ which best preserves the induced graph metric. Current approaches to solving the stress model for a graph with $|V|$ nodes and $|E|$ edges require the full all-pairs shortest paths (APSP) matrix, which takes $O(|V|^2 \log|E| + |V||E|)$ time and $O(|V|^2)$ space. We propose a novel algorithm based on a low-rank approximation to the required matrices. The crux of our technique is an observation that it is possible to approximate the full APSP matrix, even when only a small subset of its entries are known. Our algorithm takes time $O(k |V| + |V| \log |V| + |E|)$ per iteration with a preprocessing time of $O(k^3+k(|E|+|V|\log|V|)+k^2 |V|)$ and memory usage of $O(k|V|)$, where a user-defined parameter $k$ trades off quality of approximation with running time and space. We give experimental results which show, to the best of our knowledge, the largest (albeit approximate) full stress model based layouts to date.
So you want to look at a graph, part 2
This series of posts is a thorough examination of the design space of graph visualization (Intro, part 1). In the previous post, we talked about graphs and their properties. We will now talk about constraints arising from the process of transforming our data into a visualization.
HCL color space blues
I’ve been playing around with the HCL color space. HCL, if you’ve never heard of it before, is a color space that tries to combine the advantages of perceptual uniformity of Luv, and the simplicity of specification of HSV and HSL. HCL is an improvement over HSV and HSL, but it is not exactly ideal: there is a nasty discontinuity at some bits of the transformation! I have been trying to find a way around this, but I’m stumped. Let me explain, and maybe you can help me.
So you want to look at a graph, part 1
This series of posts is a tour through of the design space of graph visualization. As I promised, I will do my best to objectively justify as many visualization decisions as I can. This means we will have to go slow; I won’t even draw anything today! In this post, I will only take the very first step: all we will do is think about graphs, and what might be interesting about them.
So you want to look at a graph
Say you are given a graph and are told: "Tell me everything that is interesting about this graph". What do you do? We visualization folks like to believe that good pictures show much of what is interesting about data; this series of posts will carve a path from graph data to good graph plots. The path will take us mostly through well-known research results and techniques; the trick here is I will try to motivate the choices from first principles, or at least as close to it as I can manage.
The Beauty of Roots, a Facet demo
John Baez over at his new blog Azimuth has a post with an amazing looking fractal: the set of all roots of all polynomials with coefficients -1 or 1. Since it’s “just” a set of points, it seemed like the perfect opportunity to try Facet on a large, good-looking dataset, and here is the result. I think it looks pretty nice. If you want to know more about the mathematics behind it, read Baez’s post. If you care about the visualization details of this, read on!
Announcing Facet, the EDSL for WebGL visualization and graphics
Facet is a Javascript library I’m writing, part of a research project on high-performance visualization and graphics on the web. It’s peculiar how historical accidents are opportunities in disguise. If everyone knew Lisp, and if Javascript and the WebGL shading languages were Lisp, Facet would be what everyone would write. But Javascript is no Lisp, and WebGL’s vertex and fragment programming languages aren’t Lisp either, and many people still don’t know about Lisp.
Topology Verification for Isosurface Extraction
Tiago Etiene, Luis Gustavo Nonato, Carlos Scheidegger, Julien Tierny, Thomas Peters, Valerio Pascucci, Mike Kirby, Claudio Silva. IEEE TVCG, Accepted.
The broad goals of verifiable visualization rely on correct algorithmic implementations. We extend a framework for verification of isosurfacing implementations to check topological properties. Specifically, we use stratified Morse theory and digital topology to design algorithms which verify topological invariants. Our extended framework reveals unexpected behavior and coding mistakes in popular publicly-available isosurface codes.
How many VisWeek papers could the NYT write in three weeks?
Last week’s VisWeek finished with Amanda Cox’s amazing capstone talk about the visualization work that goes on at the New York Times. As everyone in the room was rightfully being blown away by the incredible productivity of their graphics department, Tim Lebo asked: How many papers could NYT submit in 3 weeks?
This same sentiment echoed in the hallways after her talk. Now, I don’t know what this number is; but I know what it should be. It should be zero! NYT obviously has much to say about visualization, but there is an important distinction. I think it is important to not confuse the top-of-the-line visualization practices as seen in the NYT with what we do at VisWeek. Let me be more specific.
VisWeek 2011 day 2
The VisWeek keynote is just over; the fast-forward and the first VAST session are now underway. There’s more VAST in the afternoon, and also what I think will be a great panel.
VisWeek iOS app
There is now a free iOS app where you can browse conference programs, including VisWeek. No more losing that little piece of paper with the program!
About me
I'm a researcher at AT&T Labs–Research, in the Information Visualization group. I work in data visualization, geometry processing and computer graphics. Opinions here are all mine.