The growth of the discipline of graph theory in recent years has led to a concomitant expansion of computational graph theory as witnessed by the increasing number of journal articles (and entire journals) devoted to the subject.
At least a dozen different graph drawing programs have been developed for widespread distribution. Some of the more wellknown among these include
the Discrete Mathematics routines within Mathematica and the allied Combinatorica project [Pemmaraju2003],
the Graph Editor Toolkit from Tom Sawyer Software [Madden, 2003], and
the opensource project Graphviz at AT&T [Elsen2000].
yEd graph editor (see http://www.yworks.com/en/products_yfiles_practicalinfo_demos.html ) is a powerful and flexible tool with widespread applicability to circuits, mazes and other graph application areas.
The Combinatorica project also includes a Graph Editor which can be viewed in applet version at http://www.combinatorica.com/. While most of the above projects are far more mature than Grapher, so far as we can tell, Grapher is the only one which provides all three of these: a simplified and contextsensitive GUI interface, webbased requiring no installation, and opensource.
Existing software can generally be divided into two groups: that which is algorithmintensive and that which is interfacedriven. The algorithm intensive software enables investigators who are involved in a specialty area like graph visualization or graph coloring to work effectively using powerful approximation algorithms for typically NPcomplete and NPhard problems. The interfacedriven software typically has incorporated few complex algorithms, but is software in which the development efforts have focused on creating natural interfaces that are easy to learn and use. The Grapher program described here belongs to this category, though it is intended that more complex algorithms may be added with comparative ease (owing in part, to JavaScript's ability to view functions as data).
We also make the claims that the time to learn to use Grapher will be less than most of the others and that the user of the program will be able to draw and modify small graphs more quickly with Grapher than with other applications. Having no data to justify this claim makes it premature, but I would invite those fluent in the use of another program to try Grapher and to dispute this claim. In the six years that the webbased VML version of grapher has been used on the web, no negative feedback has been received by people using the program, but much positive feedback has been. In support of the claims about ease of use, we also present some drawing “protocols” later in the paper to demonstrate why the claim about ease of use is plausible.
As computational graph theory has grown, the desirability of shared file formats for researchers to exchange graphs has as well. DIMACS format [DIMACS 1993], from the Center for Discrete Mathematics and Theoretical Computer Science, and Graph Description Language (GDL) [AiSee, 2003] have each met with some popularity in graph theoretic software applications. The more recently proposed GraphML specification [Brandes2002] has the advantage of being XMLconsistent and, hence, more easily incorporated into applications in a networked environment. Grapher uses an XMLbased file format similar to GraphML, so that adding the ability to export and import in GraphML format is anticipated to be straightforward. Additional discussion of the file format used by Grapher is found in a later section.
Several years ago, when I developed the VML version of the program , graph visualization was all the rage in graph theoretic circles. Generally, I think, this interest followed the funding cycle, driven in part by attempts to visualize very large graphs like the Internet. Some within that community, on seeing Grapher/VML expressed that they saw little value of a drawing program that dealt with small graphs, constructed by hand. Web applications, were at the time, a relatively new concept and that aspect of Grapher seemed to be of little interest. Researchers were accustomed to purchasing licenses of complex software and, often, having their technical support staff install it for them in offices and classrooms. I think they may have missed the point. Let us address the issue of why to build such a program in two ways: First, the demand seems to have increased; the number of projects allowing the handcreation of graphs has increased rather than dwindled in that time. Second, let us point out just a few of the reasons a graph theorist may want a userfriendly simplified interface for drawing graphs. An obvious reason is for the lecturer teaching graph theory in a classroom (the first author of this paper falls into that category). Another reason has to do with the nature of the discipline. Graph theory has a strong tendency to be visual ^{[}1] But unlike other branches of mathematics that might also have a strongly visual nature, graph theory is as some have said “a mile wide and an inch deep” ^{[2]} The discipline thrives on the invention of new properties about graphs, the posing of conjectures and the discovery of counterexamples, with theorems themselves generally having little widespread repercussions or future impact. Properties of graphs are numerous and relatively easy to discover or invent. ^{[3]} From our own graph theoretic research, we illustrate four original problems that we think raise interesting questions relevant to graph theory and for which we think a tool like Grapher may help to investigate.
a) Metricessential nodes of a graph. Consider a metric space in which all distances are integers (a discrete metric space). What is the smallest graph (bivalent with all lines having a length of 1) in which that space can be “modeled” within the graph as follows? All points of the metric space become nodes in the graph (and we add possibly other nodes) . Connections between these and other (possibly added nodes) are drawn until the graphtheoretic minimum distances between pairs of nodes in the graph matches exactly the metric distances? This question was initially investigated in [Dailey2] On the Graphical Containment of Discrete Metric Spaces.Discrete Mathematics, 1994, 131, 5166. Elsevier Science. . It is trivial that all metric spaces can be modeled by a graph, but what is the smallest? I proved a number of small theorems including that the tree is the smallest container of the metric space defined on its leaves. (ie., given a metric space which represents distances between end points in a tree, the tree may be uniquely reconstructed just from the distances on the leaves). But it became clear that determining which nodes in a graph are “metric essential” in the sense of being required of a smallest container was not easy to ascertain for even a small graph of say 10 or 20 nodes. Allowing the graph theorist to build such a graph and then run an algorithm to answer that question for the given graph would be immensely useful in formulating conjectures appropriate to further investigation of the area.
a) the “Euclidean dimension” of a graph. Start with a collection of points in Euclidean nspace. We begin to draw a graph as follows: let each point become a node. Then for some threshold d (a positive real number) form an edge between any pair whose distance in the space is less than d. Observe that when d is very large then the graph will be the complete graph and when it is close to zero the graph will be completely disconnected. Call the resulting graph "nEuclidean", since it can be constructed in nspace with the above technique. The natural questions are then: what graphs are nEuclidean and, alternatively, what is the smallest n such that a given graph is nEuclidean? Clearly Kp (complete graph on p nodes) is 1Euclidean since we merely choose d as the maximum distance as the points are laid along an edge. Cp (the cycle on p nodes) is 2Euclidean but is not 1Euclidean for p>3. The proof is trivial. Kp,1 the pstar (complete bipartite graph with p nodes in one component and one in the other) is 1Euclidean for p<3; 2Euclidean for 2<p<6; 3 Euclidean for 5<p<12 – That is, it becomes the sphere packing problem. A former colleague of mine, Frank Morgan reference personal communication reference showed that for each n, there is an nEuclidean graph – which is a nice and rather fundamental result. A variant of this premise is illustrated at http://srufaculty.sru.edu/david.dailey/svg/graphs10.svg where a fixed threshold d is chosen but nodes are allowed to move about such that connectivity changes. The problem is thus related to wireless networks since there is a radius around each node which governs its connectivity. I first investigated these graphs a bit in my doctoral dissertation reference/reference as an alternative way of generating random graphs, but don't recall ever seeing anyone else doing anything with them ^{[4]}.
Gravitational flavorings of graphs Dr. Deborah Whitfield of SRU has recently joined me in work I actually began just before GrapherVML was built and was a part of the reason for building Grapher/VML. The notion is this: suppose someone is exploring a graph. How might its connective structure influence the navigation process when the navigator can see only local information (possibly augmented by memory of where she has been and the various pathways traversed)? Furthermore, how might that graph be “decorated” in ways which would facilitate this navigation? And further, are certain graphs intrinsically more navigable than others, perhaps lending themselves more naturally to such interior decorating. Extrapolating a bit from how humans navigate in three dimensions of Euclidean space, we observe that gravity provides a convenient reference point on earth, but that additional guides such as landmarks and access to a magnetic field (north/south) help immeasurably. Gravity together with magnetism are enough to find shortest points between any two points on earth’s surface unless one starts at one of the poles. So in an arbitrary graph, which is a nonEuclidean metric space, what cues might we introduce to enhance people’s navigation. That is, may we introduce a “field effect” by “flavoring” (i.e., associating) the nodes of a graph with vectors of numbers representing gravity, magnetism or other properties so as to provide navigational cues to humans? Phrased a different way, which graphs are thusly flavorable, and by what process might we flavor them so as to foster navigation by a simple greedy algorithm? It works thusly. We assign an ntuple of integers (in the range 1 to p), called a flavoring, to each of the p nodes of a graph. An explorer is then assumed to work with a greedy algorithm that looks ahead at all its possible next moves (those nodes adjacent to its current position) and chooses its next move on the basis of the similarity of the flavoring of those nodes to the flavoring of the intended destination. A walk through the graph is thus motivated by the flavoring. A graph is called nflavorable if the assignment of a ntuple to each node is sufficient to allow the greedy algorithm to find a shortest path between any pair of nodes, that is if the flavoring guides simple navigation. Interestingly, the graph Pn x Pm (the multiple of two simple paths resulting in a cityblock grid consisting of n by m squares, which seems so intrinsically twodimensional can be flavored with a single dimension of gravity so as to allow shortest paths to be found on the basis of that cue, for any pair of nodes. The problem is relevant to things like designing web sites (graphs) so that people may find the pages (nodes) that they need, or flavoring (providing navigational cues) a collection of web sites (nodes) in the Internet (the graph) so that people may get where they are going using fewer steps (shortest path). Alas, as an aging graph theorist, I found that in investigating the flavorability of small graphs, it was very difficult to calculate or examine manually without the use of a computer.
The tile number of a graph
All planar graphs can be drawn with straight lines. We define the tilenumber of a planar graph as the minimum number of distinct (noncongruent) polygons from which a graph can be drawn using polygons as faces. For example the infinite planar fiveregular graph consisting of unit squares and equilateral triangles (known as the tiling 3,4,3,4,3) and seen as background on my web page at http://srufaculty.sru.edu/david.dailey/ can be constructed using just a unit square and an equilateral triangle; hence its tile number is two. I showed once that coloration of planar four regular graphs was NPcomplete and also that uniqueness of colorability was NP complete. [Dailey1] The question is if the graph coloring problem can be reduced even further: is threecoloration of planar graphs having tile number of one or two (very simple nonperiodic tilings) NP complete? If so the class of “interesting” problems can be easily constructed at random. ^{[5]}
In all four of these cases, determining these properties of graphs for even very small graphs is not intuitively obvious. In the case of gravitational flavorings of graphs, resolving even the simplest of conjectures has been extremely difficult. In the case of the first three problems an exhaustive search of possibilities would be computationally prohibitive for large graphs, but we do not need large graphs to resolve conjectures nor to gather initial evidence to suggest those conjectures. Indeed, the graph theorist often posits a constellation of properties (such as planar graphs with diameter bounded by d and D) and then looks to see if some property (such as being Hamiltonian or connected or 2Euclidean might apply). Many of the developments in graph theory over the past 40 years have begun with a mathematician noticing some pattern within graphs (the crossing number, coarseness and thickness, the node domination number, page number, and countless other properties of graphs have been studied mainly after 1970) and then experimenting with other properties of these graphs to see if theorems may be proven. Each such property represents an area of study that began with rather simple theorems suggested by experiments on small graphs. Having software that allows the graph to be easily drawn for subsequent storage and analysis is the primary purpose of this software
One additional byproduct of the program worth mentioning for the practicalminded reader, that is a part of applied graph theory is that Grapher can be used for the topdown design of web sites. Once a graph is designed, it is relatively trivial to let each node represent a web page with edges between nodes translating into hyperlinks (HTML <a> tags) between pairs of web pages ^{[6]}. This would allow the designer to think about and design intrasite, interpage connectivity from the top down. Research on how people’s knowledge and learning are affected by how the paths through which they explore connected clusters of information (such as the narrative text) have been ongoing since the 1960’s. From that research, the question is motivated as to whether some website topologies may be better than others for either teaching, providing access to information as in a library or in selling products. Various versions of Grapher enabling one to design the topology of websites (namely the graph theoretic connections between pages), has been one of the program’s capabilities since the mid1980’s ^{[7]} . This feature will most certainly be incorporated into future versions.
The original environment (cT on Andrew workstations) was a worthwhile exercise. The code was written in cT but that language had the property that with no modification whatever, the same code could run either on a Mac or on a UNIX workstation (Sun, IBM RT, etc.). Moving it to a Java applet had the advantage of web accessibility. VML/Javascript version was considerably faster than Java, and the code was more modular with the event management and drawing routines all using JavaScript that was easier to maintain with student support. The JavaScript code showed signs of being more robust than the Java Applets which at the time were undergoing a transition between layout mechanisms (swing and awt). The one disadvantage of VML was that it ran only in IE, but at the time IE had about 97% of the browser market and SVG ran nowhere without a plugin. However, with the expansion of browser support for SVG and with the consistency with W3C specs for CSS, HTML, and DOM, SVG showed better integration with the browser environment. Both VML and SVG are dialects of XML, but SVG was richer, broader and crossplatform support (while proving tricky to sort out for all aspects of the project) does exist. SVG just makes more sense in the long run. We are interested in making sure that Grapher can run across browsers, and since we feel no inordinate distaste at requiring users to download the Adobe plugin, and since we are confident that new developments in support for SVG in IE are forthcoming, we are pleased with our progress to date.
The VML version was longer in development, but was developed by fewer people. It currently has more algorithmic sophistication built in, offering approximation algorithms for node coloring, domination and graph embedding. The SVG version has code that is considerably more modular and better written, and the userinterface has been both modified to adapt to multiple browsers and several aspects have been extended and simplified to (we think) aid the user in accomplishing the various tasks involved in drawing. The navigation and undo panels are unique to the SVG version.
Because of its large number of specialized subfields, graph theory is unlikely to have a oneprogramfitsall solution for software. Both commanddriven and pointandclick interfaces have their place in the broader world of graphics software (e.g., AutoCAD vs. Photoshop), and such is likely the case in graph theory as well. Commanddriven interfaces may prove superior for generating very large graphs with numerous partial automorphisms (such as used in visualization or wireframe applications). A more heterogeneous graph would be predictably more tedious to create in a commandbased interface, suggesting that a graph theorist attempting to find counterexamples to a given conjecture, might favor the "drawing" approach.
In many of the popular pointandclick vector graphics programs (such as Adobe Illustrator, CorelDraw, Canvas and even Microsoft PowerPoint) objects are selected by clicking on them. Most importantly from an interface perspective, toggling between three important modes of drawing: object selection, object creation and object repositioning happens automatically, or at least, simply. That is, state or mode is recognized by the software, rather than requiring overt user action, hence simplifying the user's task. Let us illustrate with an example from graph theory.
Suppose we wish to draw the complete graph on three nodes, K3. In a modal program such at Combinatorica's Graph Editor, the sequence of user actions could be described by either of the following user activity protocols:
Table one
P1  P2 

The notation (Lxy) means a edge between nodes x and y is established.  


A few comments should be made about such an interface:
Each mode change requires, in fact, one click to activate the relevant menu, a mouse repositioning to choose the relevant option, and another click to activate it, in addition to the desired action (clicking at an xy coordinate to actually create the node). (That keyboard shortcuts could be used instead is really beside the point: the number of actions is still roughly equivalent from the perspective of cognitive demand on the user.) Such mode changes are, therefore, relatively expensive from a motoric, cognitive, and temporal perspective, though we might expect the cognitive and temporal expenses to decrease a bit with practice.
While Protocol P2 involves considerably fewer steps (because of fewer mode changes) than P1, it requires the user to know, in advance, “where” he or she is going (that is, what the graph will look like in advance). It may also require a bit more planning to get there. As the graph theorist experiments with a new conjecture in search of a counterexample, graphs are not always constructed with an endstate that is clearly known beforehand.
While the interface for building a edge (click on node1, drag and release over node2) appears intuitive (corresponding generally to the way one draws a graph with pencil or chalk), it may place more demand on the user's motor skills than is strictly required. An interface that allows one to affiliate nodes with simple clicks, rather than drag and click may be motorically easier and hence quicker.
A preferable interface might be gleaned from the following protocols:
P3  P4 

Note: the notation (Lxy) means a edge between nodes x and y is established.  


Table 2. Typical user event protocols to create K3 in a contextsensitive interface.
Throughout, the term "Standard Interface" will be used to refer to the now standard graphical user interface (GUI) developed for the Macintosh and later adopted in Microsoft Windows. The term "Standard Drawing Interface" refers to those elements of interface shared by the primary microcomputerbased vectororiented drawing programs such as MacDraw, Adobe Illustrator, Canvas, and CorelDraw.
In accordance with the above remarks, Grapher was developed with specifications pertaining to overall purpose, event management, data structure, algorithms and commands, user help and hints.
The program should be usable directly over the web. JavaScript is the natural language of choice here. Since JavaScript is interpreted by the browser, no plugins, downloads, or compiles are required. Source code, byte code, data, and executable image are all one and the same and are written in a language understood by an unprecedented number of programmers. Users may begin experimenting with the software by merely visiting a web address. Unlike Java applets, JavaScript creates SVG and renders the entire web page, directly.
A summary of Grapher's basic event management may be seen in Table 3.
Click on blank space  Click on unselected node  
standard  with Shift key  standard  with Shift key  
No Nodes Selected  Create new node  Rubber band Selection begins  Select clicked node  Select clicked node 
Some Nodes Selected  Deselect all nodes  Rubber band selection begins  Negate link status between clicked node and each selected node  Add node to selected node set 
Click on selected node  
standard  w/ Shift Key  Click and Drag  
Make clicked node the most recently selected  Remove node from selection  Move all selected node based on dx and dy for most recently selected node 
This event management conforms to the following specifications:
A single mouse click should be sufficient to create or select a node. Clicking on a node should select it; a click on blank space should create a node (in both cases we assume no nodes are already selected).
Two mouse clicks should suffice to connect two nodes. Clicking on the first should select it; clicking on the second should connect the two. It can be argued ^{[}8] that two clicks are motorically easier than clickdragrelease. Mode change (into "create edge" mode) can be autosensed.
To delete a node (and associated edges), one should be able to select it and then hit the delete key. (Standard Interface).
To disconnect two nodes, one should be able to click on each of the nodes (as if to create an edge). If the nodes are already connected, they become disconnected  otherwise as in #2 above, they become connected.
To move a node, one should be able to select it by clicking on it (mousedown), then to drag and release (mouseup). This is consistent both with the Standard Drawing Interface and with the Standard (Mac/Windows OS) Interface and will therefore be familiar to many users .
To label a node, it should suffice to select it, enter “label mode” and then begin typing. Cessation of typing should be signaled by either deselecting the node, or hitting the "Enter" key. (The VML version of the program
To select more than one node while some are already selected, one be able to hold down the shift key which clicking on additional nodes. Shiftclicking on an already selected node should deselect it. (Standard Interface).
Actions associated with selections of more than one node should behave similarly to the handling of a single node. Specifically, as in #3, hitting the delete key should delete all selected nodes. As in #2, clicking on an unselected node which others are selected, should connect all selected nodes to the target. As in #5, dragging a selection should behave like dragging a single node. Most drawing programs position the selection relative to the last object dragged (rather than the first or the centroid) and this seems, therefore, the preferred approach. Likewise, if more than one node is selected and keyboard activity ensues (while in “labeling mode”), then keystrokes will be appended to all labels.
The parts of the software devoted to interface and to algorithms should be separable and modular. New algorithms (for example to minimize crossing lines in a planar embedding, or to find the chromatic number) should be able to be incorporated as modules with relatively little need to adjust the primary interface. JavaScript's string and array handling, its facility with XML DOM, its objectoriented nature and the availability of lambda functions all show promise here. ^{[}9]
As a graph is grown and developed by the user, new nodes and edges should be easily created and just as easily deleted.
The graph is thusly implemented as a collection of nodes, each of which is an object consisting of a number, a unique id, a label, an x and y coordinate, and collection of links to other nodes. Each time the function to create a new node object is invoked, routines to create a new SVG <rect> and to insert this object into the SVG document are executed, in addition to the creation of the new virtual instance of the node within the data structure in script.
Basic commands are accessed either through keyboard shortcuts or through a collection of menus basically divided into the standard "File" and "Edit" categories as well as "Select" “Panels”, “Mode” and "Help".
A brief overview of each of these will be provided. We are working on expanding our contextsensitive help, and our explanatory information that accompanies the program but here is a brief synopsis of the major features to date:
File: here is where graphs may be saved and imported. While the VML version had a way of reading and writing files to local file space directly using ActiveX features within IE, no crossbrowser way seems yet to enable this. Hence import and export are mediated through a textarea from which the user may copy and paste between grapher and local file. Additional methods are being explored.
Edit:: In this menu are options for undo (including an undo buffer of up to 10 steps); redo; copy (the selected subgraph); paste; extrude (multiply selected subgraph by a line ); scale (to resize the graph's lines), and complement (forming the complement of the selected subgraph).
Select: expand (take the union of all direct neighbors of the nodes in the selection); invert (deselect the current selection and select all others); all; none and shortestPath.(given two selected nodes, return a selection containing all nodes in a shortest path).
Panel: actions (an undo panel containing by name, the last 10 actions for each of investigating previous versions of the graph). Navigation ( a set of sliders for adjusting the scale of view as well as the size of the drawing canvas). Message, a small panel left for debugging purposes.
Mode: normal (the default); label (must be toggled on or off to allow the labeling of nodes). Realign (a future mode that allows node’s connections to be modified based on their onscreen proximities to other nodes.
Help: Context help: help which tells you what can be done based on the current position of the mouse and the mode. A help file that gives basic funtions and their keyboard shortcuts. An about file telling about the grapher project.
When Grapher for VML was built, Internet Explorer completely dominated the browser market. VML is IEonly. Accordingly many design decisions were made in that environment to make the program consistent with the “Standard Interface. “ In particular copy, paste and select all were CTRL C, CTRL V and CTRL A, respectively just as users using any of a variety of interfaces descended from the Macintosh UI would expect. Unfortunately, as the browsers arena has diversified and even as IE itself has changed, some of the affiliations between control keys and behavior have been appropriated by browser developers. Despite a good healthy effort at providing similar key mappings between the VML version and the SVG version, we made the somewhat painful decision to abandon the use of the Control key as a part of our keyboard shortcuts. The browsers all seem to appropriate differently. It is of note that many features of the VML program are now no longer functional, since tabbed browsing and other evolutionary changes within IE have taken those key mappings for browser functions. Instead we use single alphabetic keys to perform such tasks: C, V and A for copy, paste and select all.
Grapher currently has been tested without major problems in Chrome, Firefox, Opera, and Safari. This version of Grapher is only compatible with Internet Explorer (versions 4 and higher should all work) with the SVG plugin from Adobe.
As a “web application” Grapher in both its SVG and VML incarnations suffers from the fact that the web has historically made the reading and writing of files to local file space difficult at best, and generally speaking, browser designers have tried to make this task impossible. In the 2003 VML version of Grapher, I was able to use very tricky ActiveX components to export and import files from within the browser. It turns out that some of these techniques were fragile and did not survive the transition from version 4 of IE to subsequent versions. So until the HTML WG is done with its work on HTML5, or until SVG 1.2 is widely adopted, reading and writing files to local file space is currently done in Grapher (SVG) using the clipboard – copying and pasting data from a desktop application (that has access to local file space) into the web application (through a textarea). We would have used the native SVG <textArea>, obviously, if that were already deployed in browsers. At this time it seems only to be available in Opera, however. ^{[}10]
By the time of the conference, we may enable some small amount of serverside storage space to allow storage of graphs remotely for a short time, thence allowing users to download the files from the server. The first author's distaste for using servers to do what should be possible locally (if only the browser manufacturer's could agree on any of a number of safe modes) did not persuade my students that this particular idiosyncracy of mine needed to stand in the way of progress. We will have some way of exporting files, other than through the clipboard soon. In truth the issue related to two other types of functionality that we do in fact desire. One would be the creation of a collaborative graph library. How such would be maintained and where it might be stored are not clear at the moment. The other would be the ability to convert graphs into web sites, as mentioned later in the paper.
While some might argue that the format we have developed for storing data is not as it should be, our perspective has been that it is adequate for now and that another natural format to consider: GraphML, (See http://graphml.graphdrawing.org/primer/graphmlprimer.html) while available, does not meet some of our needs. For example, as a drawn object, a graph in Grapher has intrinsic x and y coordinates for its nodes. Its nodes and lines have particular shapes. An abstract graph, as a pure binary relation, has none of those features required of its instantiation. Grapher, though, is a pointandclick interface for building graphs. It has, as such, coordinates and other physical manifestations of the graph that are essential to the interface itself. Attributes such as the label of a node, its location, or its color are directly related to its status as a visible object. Accordingly, and perhaps through our naïveté concerning the GraphML notation, we have moved in a different direction but without so much conviction that we resist future conversion.
From a different perspective, some might argue that one should limit oneself in the development of an XML language to very few attributes and to attributes that have only a finite number of possible values, the GrapherML language that we have adopted follows much of SVG’s lead in this regard: things that have visible instantiation like <rect> and <line> in SVG likewise will have direct manifestations in a drawn graph like <node> s and <edge>’s of those properties as attributes rather than as child nodes in the DOM. That is rather than stating something like this
<node> <attribute><coordinate axis=”x”>123</coordinate></attribute> <attribute><coordinate axis=”y”>654</coordinate></attribute> <attribute><presentation attribute=”color”>red</coordinate></attribute> </node>
that would ring true to the initiative to avoid attributes in our XML languages, something like
<node x=”123” y=”654” color=”red”>
is a bit less verbose ^{[11]}. Not that GraphML would be as verbose as shown in this example, but it is not clear from the GraphML primer quite how one would specify physical aspects of the graph without relying on SVG inside the node and edge declarations. We also advance the suggestion that a majority of folks conversant with SVG will be comfortable with the compromise between legibility, standardizability, and verbosity that we’ve adopted.
Below is a drawing of the triangle K3
<graph> <node id="g0" x="100" y="100" color="#fa8" label="happy"> <edge to="g1" /> <edge to="g2" /> </node> <node id="g1" x="50" y="150" color="#faa" label="hamburger"> <edge to="g0" /> <edge to="g2" /> </node> <node id="2" x="150" y="150" color="#8af" label="artichoke"> <edge to="0" /> <edge to="1" /> <edge to="3" /> </node> <node id="3" x="200" y="100" color="#fa8" label="didapper"> <edge to="2" /> </node> </graph>
As noted under the Help section above, there is already context help, as well as a brief reminder card concerning basic command built into the help menu within the program. We hope to develop a more extensive manual at some time. For now we have afew illustrations of the process of drawing a few familiar graphs: W7, the wheel with seven spokes, and the Peterson graph, a three regular graph on ten nodes.
And now a slightly more complex drawing
Any project of this size generates a wish list. We have begun assembling such a list but have not yet begun prioritization. It might prove to be a good time to send us your list of desired features too! Contacting the first author would be the appropriate way to do this at the current time. Here are some of the things we have currently set our sights on:
Certain standard redrawing options, like rotation, randomization of positions (as shaking or completely reworking at random) and the like, as well as certain graph theoretic options like finding dominating sets,
Having a panel with a slider that adjusts the distance threshold for Euclidean graphs,
A graph coloring engine such as that in Grapher VML .
A node domination engine such as that in Grapher VML
Improved layout heuristics for planar embedding
The ability to export web site “skeletons” web pages with interpage connectivity
generated from links between nodes in grapher
Certain common graph statistics should be easily displayed. The subgraph induced on a selected set of nodes should be easily, or perhaps automatically, queried for its number of edges and nodes, and perhaps, as well, its connectedness, diameter, and so forth. Single nodes should have their degrees revealed. Selecting a pair of nodes, should reveal its pathwise distance.
Given a collection of more than two nodes, the ability to find a spanning tree and to display statistics about that spanning tree would be nice.
Likewise, the ability to reselect a previous selection proves useful at times. This was implemented in Grapher/VML and was quite handy at times.
The collection of a library of all small graphs (as in Harary's book).
A library of "interesting" graphs such as the Tutte graph, the Peterson graph, crossover graphs, etc.
Ways of making new algorithms easily added: a simplified code editor.
allow the selection of nodes based on attributes such as node degree, label or color.
incorporation through a union operation, of stored graphs into a current working graph
We are very much interested in sharing the code base as well as the interface concepts that we’ve developed. None of the authors has experience with large collaborative open source projects so we will be seeking guidance from others in the SVG and other communities that do have these experiences. Please feel free to email the authors with suggestions, or more importantly offers to help!
[Pemmaraju2003] “Computational Discrete Mathematics : Combinatorics and Graph Theory with Mathematica”. Copyright © 2003 Cambridge University Press.
[Dailey2] Discrete Mathematics v. 131. Elsevier Science. “On the Graphical Containment of Discrete Metric Spaces.”. Copyright © 1994 Elsevier Science. 5166.
[Wormald3] Surveys in Combinatorics . Elsevier Science. “Models of random regular graphs..”. Copyright © 1999 Elsevier Science. 239238.
[Matula1972] In R.C. Read (Ed.) Graph Theory and Computing. . Academic Press. . “Graph Coloring algorithms”. Copyright © 1972 Elsevier Science. 239238.
The Graph ML file format. Copyright © 2002 Graph Drawing Steering Committee http://graphml.graphdrawing.org/.
Graphviz  open source graph drawing software. Copyright © 2000 AT&T Research. (http://www.research.att.com/sw/tools/graphviz/)..
^{[}1] though the blind topologist Bernard Morin may come to mind for some as a possible counterexample, as well Lawrence Baggett with whom I was acquainted during my own graduate education in Colorado).
^{[2] } I first heart this description from my friend Tom Head of SUNY Binghamton who mentioned it as a description he had heard from unnamed others.
^{[3] } My friend Frank Harary and I would argue about this: he was adamant that graph theory was discovered while I believed fundamentally that it was invented through a process so constructivist (in either the psychological or mathematical sense) that new properties might almost be discovered by automata.
^{[4] }Though Svante Janson does look at differing properties of graphs generated with different methods at referenceJanson, Svante; Random Graphs, seen at http://eref.uqu.edu.sa/files/random_graphs__151190.pdf reference
^{[5] }I am not sure whether Nick Wormald’s results on random regular graphs [Wormald3] cover the related issue or planar fourregular graphs or not
^{[6] }Technically the WWW is a directed graph, but because all major browsers implement a back button it does has some of the properties of an undirected graph at least when it comes to random walks for example and the ability to sometimes traverse a directed link backwards.
^{[7] } when the nodes became leaves of a hypertext or cards in a Hypercard stack, rather than pages in a web site
^{[8] }Fitts' law suggests that the size of a target predicts the difficulty of clicking on it. Since nodes are likely to be fairly small (since we wish to display many of them onscreen) we wish to seek the mousetargeting task as simple as possible. Allowing the wrist the greater relaxation of not having the mouse button held down while pursuing the target makes intuitive sense. Compare, for example, Inkpen, 2001, which analyzes children's skills with the mouse. Furthermore since the set of nodes to draw lines from (the selected set) consists frequently of more than one node, the origination of the drag action would be ambiguous.
^{[9] }The earlier VML program treated functions as data to incorporate approximation algorithms for node coloring, node domination and graph layout. The SVG version will have something like this soon.
^{[10] } The ability to open an HTML window through script running in SVG defied our abilities to make it happen in IE/ASV, so ultimately we were forced to embed the SVG in an HTML <object> and created the textarea within the parent HTML container. While we would have preferred not to have to do this, a week’s effort of experimentation failed to produce fruit.
^{[11] }and more appealing to those who learned to program in Fortran in the dark ages when verbosity was verboten and programs had to compile and execute in 16K of machine memory