MosaicSets: Embedding Set Systems into Grid Graphs

Area of Science:

• Information Visualization
• Computational Geometry
• Operations Research

Background:

• Visualizing relationships between sets is crucial in information visualization.
• Existing methods struggle with non-spatial set systems and contiguity constraints.
• Representing complex set structures requires novel algorithmic approaches.

Purpose of the Study:

• Introduce MosaicSets, a new method for creating Euler-like diagrams from non-spatial set systems.
• Map elements to grid cells (hexagonal or square) ensuring set contiguity.
• Optimize overall and individual set compactness while handling NP-hard computational challenges.

Main Methods:

• Integer linear programming to find optimal element-to-grid-cell assignments.
• Relaxation of contiguity constraints for non-embeddable set systems.
• Case study using university faculty research groups, departments, and projects.

Main Results:

• Demonstrated the NP-hard nature of the optimal mapping problem.
• Integer linear programming effectively solves real-world instances rapidly.
• Developed rendering styles and evaluated performance with quantitative measures and expert interviews.

Conclusions:

• MosaicSets provides an effective solution for visualizing complex set systems with contiguity requirements.
• The integer linear programming approach offers optimal solutions for practical applications.
• Relaxation techniques enhance the method's applicability to challenging set visualizations.