Geometric Representations of Dichotomous Ordinal Data

摘要

Motivated by the study of ordinal embeddings in machine learning and by the recognition of Euclidean preferences in computational social science, we study the following problem. Given a graph G, together with a set of relationships between pairs of edges, each specifying that an edge must be longer than another edge, is it possible to construct a straight-line drawing of G satisfying all these relationships? We mainly consider a dichotomous setting, in which edges are partitioned into short and long, as otherwise there are simple (planar) instances that do not admit a solution. Since the problem is NP-hard even in this setting, we study under which conditions a solution always exists. We prove that degeneracy-2 graphs, subcubic graphs, double-wheels, and 4-colorable graphs in which the short edges induce a caterpillar always admit a realization. These positive results are complemented by negative instances, even when the input graph is composed of a maximal planar graph, namely a double-wheel graph, and an edge. We conjecture that planar graphs always admit a (not necessarily planar) realization in the dichotomous setting.