US6091424A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Labeling graphical features of drawings
Assignee: Tom Sawyer Software
•
Filing: 1996-11-01
•
Granted: 2000-07-18
•
Expires: 2016-11-01
Abstract
Abstract A method is provided for automated placement of labels for a given graph layout or map. Even though in practice a label is usually associated with a line (edge), point (node) or area, this method can be extended to produce labeling solution for any graphical feature with explicit geometric representation (in two or three dimensions). This method first finds a labeling solution for a set of graphical features G by eliminating a subset of the set of potential label placements for any member of G, and reducing the labeling problem to a maximum matching problem of a bipartite graph. Next, if there are graphical features in G that have no label placement assigned to them yet, a backtracking algorithm may be used to improve the space available for the labeled graphical features. It may be shown that the labeling problem is NP-hard if any graphical feature in G is a line or point. As a result, the GFLP problem cannot be solved in polynomial time, but requires the application of well-devised heuristics.
Inventors
- 👤 Brendan P. Madden
- 👤 Konstantinos G. Kakoulis
- 👤 Ioannis G. Tollis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:47
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/26
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
62 words
A method of assigning label positions to features within a graph drawing, comprising the steps of: identifying a subset of potential label placements from among a set of potential label placements; representing the graphical features and the potential label placements as nodes within a matching graph separate and distinct from the graph drawing; and finding a high-cardinality matching of the matching graph.
Claim 2
Independent Claim
62 words
A method of assigning label positions to features within a graph drawing, comprising the steps of: identifying a subset of potential label placements from among a set of potential label placements; representing the graphical features and the potential label placements as nodes within a matching graph separate and distinct from the graph drawing; and finding a high-cardinality matching of the matching graph.
Claim 3
Dependent Claim
37 words
The method of claim 1, wherein the matching graph is a bipartite graph, nodes within an upper half of the graph representing graphical features and nodes within a lower half of the graph representing potential label placements.
Claim 4
Dependent Claim
23 words
The method of claim 2, wherein finding a high-cardinality matching of the matching graph comprises finding a maximum-cardinality matching of the matching graph.
Claim 5
Dependent Claim
14 words
The method of claim 3, wherein each label placement has a weight associated therewith.
Claim 6
Dependent Claim
24 words
The method of claim 4, wherein finding a high-cardinality matching of the matching graph comprises finding a maximum-cardinality minimum-weight matching of the matching graph.
Claim 7
Dependent Claim
29 words
The method of claim 5, wherein each node within the lower half of the graph represents a set of label placements each pair of label placements of which overlap.
Claim 8
Dependent Claim
22 words
The method of claim 6, wherein each node within the lower half of the matching graph is of at most degree two.
Claim 9
Dependent Claim
23 words
The method of claim 7, wherein identifying a subset of potential label placements comprises:dividing the graphical layout into a number of horizontal segments.
Claim 10
Dependent Claim
15 words
The method of claim 8, wherein each potential label placement occupies only one horizontal segment.
Claim 11
Dependent Claim
18 words
The method of claim 9, wherein each potential label placement overlaps at most one other potential label placement.
Claim 12
Dependent Claim
60 words
The method of claim 6, comprising the further step of, given a matching graph in which at least one node in the lower half of the matching graph is of degree greater than two, reducing the matching graph to obtain a matching graph wherein each node within the lower half of the matching graph is of at most degree two.
Claim 13
Dependent Claim
33 words
The method of claim 6, comprising the further steps of: representing overlaps of the potential label placements using an overlap graph; and building the matching graph using information derived from the overlap graph.
Claim 14
Dependent Claim
26 words
The method of claim 12, wherein nodes in the overlap graph represent label placements and edges between such nodes represent overlap between pairs of label placements.
Claim 15
Dependent Claim
57 words
The method of claim 13, wherein building the matching graph comprises: identifying within the overlap graph connected components that are complete graphs; and for each such complete graph, inserting a node in the matching graph and connecting to the node an edge for each graphical feature to which a label placement represented in the connected component corresponds.
Claim 16
Dependent Claim
27 words
The method of claim 14, comprising the further steps of: selectively eliminating at least one node from the overlap graph; and repeating the steps of claim 14.
Claim 17
Dependent Claim
23 words
The method of claim 7, wherein finding a maximum-cardinality minimum-weight matching comprises traversing the lower half of the matching graph, selecting alternate edges.
Claim 18
Dependent Claim
49 words
The method of claim 12, comprising the steps of: selecting odd-numbered alternate edges and computing a corresponding weight; selecting even-number alternate edges and computing a corresponding weight; and finally selecting one of the odd-numbered alternate edges and the even-numbered alternate edges according to which selection gives the minimum weight.
Claim 19
Dependent Claim
69 words
The method of claim 7, wherein identifying a subset of potential label placements comprises: for a plurality of graphical features, identifying in accordance with at least one predetermined criterion areas within which labels for the respective graphical features may be placed; and based on the preceding step, identifying a plurality of regions in accordance with the number of graphical features for which labels may be placed within each region.
Claim 20
Dependent Claim
95 words
The method of claim 18, comprising the further steps of, for each region, in preferential order from regions having only one graphical feature for which labels may be placed within the region to regions having more than two graphical features for which labels may be placed within the region: determining a number of label placements for one of the graphical features that will fit within the region; if the number is zero, merging the region with an adjacent region; and if the number is non-zero, placing an equal number of nodes in the overlap graph.
References Cited (Backward Citations)
US5450535A
Cited
US5684940A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-18 | 2004-01-17 | 2004-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-18 | 2008-01-17 | 2008-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-18 | 2012-01-17 | 2012-07-18 | $7700.00 | Window Closed / Lapsed |