Company News
Berkeley, CA, July 18, 2000—Tom Sawyer Software, the leading vendor of scalable and incremental graph layout technology, today announced that it has received U.S. Patent Number 6,091,424 titled "Labeling Graphical Features of Drawings". The patent is authored by Brendan Madden, Chief Executive Officer of Tom Sawyer Software, and by Professors Konstantinos Kakoulis and Ioannis Tollis of the University of Texas at Dallas.
Tom Sawyer Software's labeling system is already included in the Graph Layout Toolkit. This key to this innovative labeling system is that every label is globally aware. As part of the label assignment process, labels avoid overlapping other nodes, edges, crossing locations, and labels. Further, this is all addressed with the linear-time algorithm family.
With this patented method label placement is automated. Even though a label is usually associated with a line (edge), point (node), or area, this method can be extended to produce labeling solutions for any graphical feature with explicit geometric representation in two or three dimensions.
The method first finds a labeling solution for a set of graphical features by eliminating a subset of the set of the potential label placements in such a way that the graph describing the labeling solution space can be made into a bipartite graph. From this particular point, the solution to the labeling problem can be found as a solution to a maximum graph matching in linear-time. Thereafter, backtracking techniques can be applied for those labelings that have not as yet been assigned. This globally optimal matching also permits tailoring options to be applied on a label by label basis providing extended customization options.
"We are pleased that our research and development in graph theory, graph layout, labeling, and computational geometry are being formally recognized by the U.S. Patent and Trade Office," said Brendan Madden, Chief Executive Officer of Tom Sawyer Software. "Our company wishes to thank Dr. Kakoulis and Dr. Tollis from the University of Texas at Dallas for their collaboration on this innovative technology."
Tom Sawyer Software is the leading provider of software and services that enable organizations to build highly scalable and flexible graph and data visualization and analysis applications. These applications are used to discover hidden patterns, complex relationships, and key trends in large and diverse datasets. Tom Sawyer Software serves clients with needs in link analysis; network topology; architectures and models; schematics and maps; and dependencies, flows, and processes. We help clients federate and integrate their data from multiple sources and build the graph and data visualization applications that are critical to analyzing and gaining insight into their data.
View All Press Releases