Daniel Archambault


Ph. D. Student at the University of British Columbia

I'm now a post-doc at Bordeaux INRIA Sud-Ouest. This page should be up for a little while longer, and I'll continue to update it while it is available.

Introduction
Hi there! My name is Daniel Archambault, and I'm a Ph.D. student here at the University of British Columbia (UBC) in the Department of Computer Science. I'm currently interested in studying several areas of computer graphics and theoretical computer science here at UBC. My thesis deals with graph drawing.

In 2001, I completed my undergraduate degree (B.Sc.H. in Computing and Information Science) at Queen's University in the lovely city of Kingston, Ontario. In 2003, I completed my Master of Science at UBC in computer science.

Here is my list of publications and submitted papers.

What are my academic interests?
I am interested in computational geometry, computer graphics, and visualization. My Master's thesis dealt with determining the set of all distant horizons of a terrain. My doctoral work consists of developing algorithms to draw large graphs. Our approach involves laying out large graphs hierarchically by topological feature by default or by using domain-specific knowledge.

Graph Structural Difference
This paper presents a technique for visualizing the differences between two graphs. The technique assumes that a unique labeling of the nodes for each graph is available, where if a pair of labels match, they correspond to the same node in both graphs. Such labeling often exists in many application areas: IP addresses in computer networks, namespaces, class names, and function names in software engineering, to name a few. As many areas of the graph may be the same in both graphs, we visualize large areas of difference through a graph hierarchy. We introduce a path-preserving coarsening technique for degree one nodes of the same classification. We also introduce a path-preserving coarsening technique based on betweenness centrality that is able to illustrate major differences between two graphs.

Publications
Daniel Archambault Structural Differences Between Two Graphs through Hierarchies in Graphics Interface 2009, to appear. paper

TugGraph
Many graph visualization systems use graph hierarchies to organize a large input graph into logical components. These approaches detect features globally in the data and place these features inside levels of a hierarchy. However, this feature detection is a global process and does not consider nodes of the graph near a feature of interest. TugGraph is a system for exploring paths and proximity around nodes and subgraphs in a graph. The approach modifies a pre-existing hierarchy in order to see how a node or subgraph of interest extends out into the larger graph. It is guaranteed to create path-preserving hierarchies, so that the abstraction shown is meaningful with respect to the structure of the graph. The system works well on graphs of hundreds of thousands of nodes and millions of edges. TugGraph is able to present views of this proximal information in the context of the entire graph in seconds, and does not require a layout of the full graph as input.

Publications
Daniel Archambault, Tamara Munzner, and David Auber. TugGraph: Path-Preserving Hierarchies for Browsing Proximity and Paths in Graphs IEEE Pacific Visualization Symposium 2009, pages 113--121. paper

GrouseFlocks
Several previous systems allow users to interactively explore a large input graph through cuts of a superimposed hierarchy. This hierarchy is often created using clustering algorithms or topological features present in the graph. However, many graphs have domain-specific attributes associated with the nodes and edges which could be used to create many possible hierarchies providing unique views of the input graph. GrouseFlocks is a system for the exploration of this graph hierarchy space. By allowing users to see several different possible hierarchies on the same graph, the system helps users investigate graph hierarchy space instead of a single, fixed hierarchy. GrouseFlocks provides a simple set of operations so that users can create and modify their graph hierarchies based on selections. These selections can be made manually or based on patterns in the attribute data provided with the graph. It provides feedback to the user within seconds, allowing interactive exploration of this space.

Publications
Daniel Archambault, Tamara Munzner, and David Auber. GrouseFlocks: Steerable Exploration of Graph Hierarchy Space. IEEE Transacitons on Visualization and Computer Graphics, 14(4):900 -- 913. paper (Follow link for source)

Grouse
Grouse is a feature-based approach to steerable exploration of a graph and an associated hierarchy. Steerability allows exploration to begin immediately, rather than requiring a costly layout of the entire graph as an initial step. In a feature-based approach, the subgraph inside a metanode of the graph hierarchy is laid out with a well- chosen algorithm appropriate for its topological structure. Grouse preserves the input hierarchy, which provides meaningful information to the user when its metanodes correspond to features of interest. When a metanode in the hierarchy is opened, a limited number of metanodes are laid out again along the path between the opened node and the root. We demonstrate the effectiveness of Grouse on datasets from IMDB, the Internet Movie Database, where nodes are actors and cliques represent movies. The combination of feature-based layout and limited relayout computation does not fragment features in the hierarchy and improves the number of levels in the hierarchy that can be seen at once over previous approaches.

Publications
Daniel Archambault, Tamara Munzner, and David Auber. Feature-Based and Steerable Graph Hierarchy Exploration. Proceedings of EuroVis 2007, 67 -- 74. paper (Follow link for source)

SPF
Quasi-trees, namely graphs with tree-like structure, appear in many application domains, including bioinformatics and computer networks. Our new SPF approach exploits the structure of these graphs with a two-level approach to drawing, where the graph is decomposed into a tree of biconnected components. The low-level biconnected components are drawn with a force-directed approach that uses a spanning tree skeleton as a starting point for the layout. The higher-level structure of the graph is a true tree with meta-nodes of variable size that contain each biconnected component.

Publications
Daniel Archambault, Tamara Munzner, and David Auber. Smashing Peacocks Further: Drawing Quasi-Trees from Biconnected components. In Proceedings of InfoVis 2006 in Transactions on Visualization and Computer Graphics 12(5):813 -- 820, September 2006. paper (Follow link for source)

TopoLayout
TopoLayout is an algorithm to layout graphs by topological features. Currently it detects trees, biconnected components, connected components, and highly connected clusters. It exploits the wealth of algorithms already developed in the graph drawing literature in order to draw each subgraph with an appropriate algorithm.

Publications
Daniel Archambault, Tamara Munzner, and David Auber. TopoLayout: Multi-Level Graph Layout by Topological Features. IEEE Transactions on Visualization and Computer Graphics, 13(2):305--317. paper (Follow link for source)
Daniel Archambault, Tamara Munzner, David Auber. TopoLayout: Graph Layout by Topological features. UBC CS Technical Report TR-2005-30. TR
Daniel Archambault, Tamara Munzner, David Auber. TopoLayout: Graph Layout by Topological features. IEEE Information Visualization 2005 Poster Compendium, pages 3 -- 4. short paper

Distant Horizon Computation
In my Master's thesis, I described an algorithm to compute all the distant horizons of a terrain. A distant horizon is the boundary between the sky and the terrain from some, horizontal, orthographic viewing direction. In this work, we demonstrate that the problem of computing the set of edges appearing on at least one distant horizon is 3SUM hard. We also provide an example of a terrain with a quadratic number of disjoint intervals of direction where an edge appears on a distant horizon. Finally, we describe an output sensitive query data structure which can return the set of edges on the distant horizon or the distant horizon itself from a specified viewing direction.

Publications
Daniel Archambault, William Evans, and David Kirkpatrick. Computing the Set of All the Distant Horizons of a Terrain. Invited submission to Selected Papers from the 16th Canadian Conference on Computational Geometry (CCCG) in International Journal of Computational Geometry and Applications 15(6):547 -- 563, December 2005. paper
Daniel Archambault, William Evans, and David Kirkpatrick. Computing All the Distant Horizons of a Terrain. Proceedings of the 16th Canadian Conference on Computational Geometry, pages 76 -- 79, 2004. paper

Voxel Colouring
A project that I undertook in Dr. Wolfgang Heidrich's course in Winter 2002. The source code and a simple viewer are available.

What are my other interests?

Astronomy
I'm an astronomy/astrophotography enthusiast. I love taking pictures of Aurora displays (who doesn't) and planetary alignments. I've managed to publish one picture in Skynews Magazine edited by Terrance Dickinson. I'm a member of RASC (Kingston Centre), and still observe and take photos when I can.

Writing
Writing is just one of those things that I need to do. I write most evenings for about an hour or so. I've written lots of short fiction, and I'm currently working on a novel. Most of it is fantasy, but there are a few sci-fi ones, and a few mixed ones. For more information on that, you should check out my writing page.

Reading
A fair bit of Science Fiction and Fantasy and the occasional main stream novel. I'm a big fan of short fiction anthologies, which means I'm a rare kind of person these days.