Institut für Theoretische Informatik, Algorithmik

GraphDroid – An Android-Based Multi-Touch Enabeld Graph Editor

GraphDroid is a graph editor for modifying graphs and their layouts in a simple and intuitive way, by exploiting the novel input methods provided by modern multi-touch devices. It uses the Android 4 framework, and should generally run on any sufficiently modern Android-based device, also on smart phones. A working version is available in the download section.

GraphDroid serves as a prototype for developing and evaluating new interaction techniques wit graphs and their layouts. Based on this framework, we also developed a graph game CycleXings, which won the first prize in the Graph Drawint Contest 2013.

Motivation

When exploring a graph or modeling a relation as a graph, it is commonly desirable to modify layouts of graphs in order to give a better overview or highlight certain structures. Unfortunately, today's graph editors give only poor support for such tasks. They typically allow to create new layouts of the whole graph or subgraphs, but when it comes to manipulating a given layout interactively, the two basic operations are picking nodes or sets of nodes in an axis-parallel rectangle and moving them in parallel. Performing complex layout changes with such tools is a tedious task, and the many precise point, click, and move operations are tiresome.

Our prototype graph editor GraphDroid overcomes these limitations of classical interfaces by using multi-touch input to provide a new interface for interaction with graphs and their layouts that is both more natural and more intuitive than previous interaction concepts. Compared to the mouse, the pin-pointing is slightly less accurate on such devices (depending on the size of the user's finger), however it is far easier to follow a complicated trajectory, e.g., one enclosing exactly the vertices one would like to select. Modern touch screens allow separate tracking of several fingers and distinguish several gestures, such as tapping, swipes, and moving two (or more) fingers independently. This allows for a rich and versatile input experience offering many degrees of freedom.

User Interface

GraphDroid distinguishes two modes navigation and creation mode and manipulation mode, depending on whether there currently are selected vertices. The change of modes is thus implicit by selection and deselection of nodes.

In navigation and creation mode, the following operations are possible:

  • selection of (sets of) vertices (tapping or enclosing in a curve)
  • creation of vertices and edges (tapping, connecting vertices by a line)
  • deletion of vertices and edges (crossing vertices and lines by a curve)
  • splitting edges (selecting an edge and moving its middle to the position of the subdivision vertex)
  • panning, rotating and scaling the canvas (using two fingers)

Second, in manipulation mode, the possible operations are

  • moving a single vertex (grabbing a selected vertex with a single finger and moving it to the target position)
  • rotating, scaling and moving the subgraph consisting of selected

vertices (grabbing the selected subgraph with two fingers)

  • copy & paste (via buttons)
  • merging vertices (moving vertices on top of each other)

It should be noted that some of these gestures are quite similar. For example, deletion and selection in navigation and creation mode is both done by drawing a curve. To distinguish both inputs, it is required for selections that the curve ends in roughly the same area where it was started, otherwise the trajectory will be interpreted as a deletion command. To support the user, both the trajectory of the curve, as well as the area for which the gesture will be interpreted as a selection command, are shown.

A second major choice we made is the handling of layout transformations when grabbing a subgraph with two fingers in manipulation mode, which allows to simultaneously scale, rotate and move the currently selected vertices. To achieve an intuitive modification experience, we distinguish two possible cases, based on the position of the selected vertices and the user's fingers. If the user's fingers are on top of two selected vertices, all modifications are done such that these two vertices will stay exactly under the fingers. If on the other hand, there are no such vertices, for example if the user starts the operation in an empty area of the screen, this kind of behavior would be counter-intuitive, and we then choose the rotation center as the center of the axis-aligned bounding box of the selected vertices.

Finally, to further enhance the interactive experience and enable the user to achieve larger layout transformations by few operations, our editor supports algorithms that are executed continually during layout manipulations and adapt the remainder of the layout that is not currently selected in response to the user's actions. As a basic example, we have implemented a spring embedder that moves unselected vertices away if a selected vertex is moved close to them. Since all vertices are tied by relatively strong springs to their original location, the mental map is preserved. Few iterations suffice to transform the starting layout, allowing for a smooth interactive experience.

Project Team

The development was financially supported by the project Entwicklung eines intuitiven, gestenbasierten Graph-Editors within the area of competence Information, Communication, and Organization" of KIT

Download

graphdroid.apk

Note that it may be necessary to first allow the installation of third-party software in the settings.