On computing optimal linear diagrams

DOI10.1007/978-3-031-15146-0_2MaRDI QIDQ6108740zbMATH OpenOpenAlexFDO

Authors Alexander Dobler, Martin Nöllenburg

Publication date 26 July 2023

Published in Diagrammatic Representation and Inference (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.08631

zbMATH Keywords

TSPNP-hardnesslinear diagramsconsecutive onesalgorithm benchmarking

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Abstract: Linear diagrams are an effective way to visualize set-based data by representing elements as columns and sets as rows with one or more horizontal line segments, whose vertical overlaps with other rows indicate set intersections and their contained elements. The efficacy of linear diagrams heavily depends on having few line segments. The underlying minimization problem has already been explored heuristically, but its computational complexity has yet to be classified. In this paper, we show that minimizing line segments in linear diagrams is equivalent to a well-studied NP-hard problem, and extend the NP-hardness to a restricted setting. We develop new algorithms for computing linear diagrams with minimum number of line segments that build on a traveling salesperson (TSP) formulation and allow constraints on the element orders, namely, forcing two sets to be drawn as single line segments, giving weights to sets, and allowing hierarchical constraints via PQ-trees. We conduct an experimental evaluation and compare previous algorithms for minimizing line segments with our TSP formulation, showing that a state-of-the art TSP-solver can solve all considered instances optimally, most of them within few milliseconds.

Recommendations

• Efficient on-line algorithms for Euler diagram region computation
• Drawing Order Diagrams Through Two-Dimension Extension
• Graph Drawing
• Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way
• Graph Drawing

Cites work

• A note on the NP-hardness of the consecutive block minimization problem
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Consecutive block minimization is 1.5-approximable
• Hardness results on the gapped consecutive-ones property problem
• Heuristic methods to consecutive block minimization
• Iterated local search for consecutive block minimization
• On the gapped consecutive-ones property
• Polynomial Complete Consecutive Information Retrieval Problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Euclidean traveling salesman problem is NP-complete
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The travelling salesman and the PQ-tree.

Cited in

(1)

• scientific article; zbMATH DE number 5006801 (Why is no real title available?)

This page was built for publication: On computing optimal linear diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6108740)