Untangled Euler diagrams

• US 8,442,930 B2
• Filed: 12/02/2010
• Issued: 05/14/2013
• Est. Priority Date: 12/02/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Riche, Nathalie Henry, Dwyer, Tim
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US12/958,419
• Publication Number:
  US 20120141972A1
• Time in Patent Office: 894 Days
• Field of Search: 706/45
• US Class Current: 706/45
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F

Abstract

A modified Euler diagram may use multiple convex shapes to display sets or members of sets. In one embodiment, a compact Euler diagram may represent members once, with the sets split into separate regions that may form a containment hierarchy over the members. The split set regions may be drawn with simple convex shapes and joined with connecting lines, which may be concave shapes. In another embodiment, each set may be illustrated with a single convex shape and the members of more than one set may be duplicated. In such an embodiment, the members may be drawn with convex shapes and joined with connectors, which may be concave shapes. The modified Euler diagrams may be deterministically created by grouping the elements into sets, organizing the sets by size, placing elements in the sets, and creating connections between the elements using a set of constraints.

Claims

1. A graph illustrating a plurality of sets and a plurality of members of said sets, each of said members being a member of at least one of said sets, and at least one of said members being a member of at least two of said sets, said graph comprising:

a plurality of elements, said elements representing said members and said sets;

a first element being displayed by multiple convex shapes connected by at least one concave connector; and

said members having a label.

2. The graph of claim 1, each of said members being displayed one time.

3. The graph of claim 1, at least one of members being displayed at least twice.

4. The graph of claim 1, said convex shapes being rectangular.

5. The graph of claim 1, said multiple convex shapes and said connector having a first background color.

6. The graph of claim 5, a second element being displayed by a second set of multiple convex shapes connected by at least one concave connector.

7. The graph of claim 6, said second element having a second background color.

8. The graph of claim 7, said first element and said second element being a first set and a second set.

9. The graph of claim 7, said first element and said second element being a first member and a second member.

10. A method performed on a computer processor, said method comprising:

receiving a plurality of members, each of said members being a member of at least one set, at least one of said members being a member of at least two sets;

creating a hierarchy of elements by a grouping method comprising;

sorting said sets by a number of members in each set, said sets being sorted from largest to smallest;

determining a membership list for each of said members, said membership list identifying sets for which said member is a member;

organizing said members according to said membership list to create a list of members, said organizing comprising grouping said members;

creating a graph by laying out said elements according to said hierarchy by a layout method comprising;

processing each member from said list of members by identifying a group associated with said set and if said group is not created, creating said group, and adding said member to a last group in said membership list; and

for each set, drawing a boundary around all groups associated with a set; and

displaying said graph on a display device.

11. The method of claim 10, said boundary comprising at least one rectangular boundary.

12. The method of claim 11, said boundary comprising a non-convex bundle path.

13. The method of claim 12 further comprising:

receiving a selection of a first group and a movement vector;

translating said first group according to said movement vector; and

recreating at least one bundle path.

14. The method of claim 13 further comprising:

determining that a member of said first group is also a member of a second group;

creating a representation of said member in said second group; and

creating a second convex bundle path from a representation of said member in said first group to a representation of said member in said second group.

15. The method of claim 10 further comprising:

determining a background color for each of said groups; and

applying said background color within said boundary.

16. A method performed on a computer processor, said method comprising:

receiving a plurality of members, each of said members being a member of at least one set, at least one of said members being a member of at least two sets;

creating a graph by laying out said elements according to said hierarchy by a layout method comprising;

for each of said sets, laying out said members within each set, at least two of said sets comprising a first member;

applying a constraint driven force directed algorithm to optimize placement of said members within said sets; and

create paths between each of said members being located in at least two of said sets; and

presenting said graph on an output device.

17. The method of claim 16, said sets being arranged within rectangular boundaries.

18. The method of claim 17, said paths having a background color.

19. The method of claim 16 further comprising:

receiving a second set of relationships, said second set of relationships comprising relationships between at least two of said members; and

overlaying a graphical representation of said relationships onto said graph.

20. The method of claim 16 further comprising:

identifying a first set being a subset of a second set; and

displaying said first set within said second set.