Geometric Realizations of Dichotomous Ordinal Graphs
Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, Antonios Symvonis · 2025
Read Geometric Realizations of Dichotomous Ordinal Graphs by Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, Antonios Symvonis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-07361.txt.
Introduction
Patrizio Angelini and co-authors study a drawing problem for networks whose links are split into short and long. Their 2025 paper asks when such a graph can be drawn so that every long link truly ends up longer than every short one, for any split of the links.
The team ties the answer closely to a graph trait called degeneracy, which counts how sparse the graph is in its densest parts. They show that sparse graphs can always be drawn this way in matching dimension, both in flat space and on a sphere, and that dense graphs cannot. They also settle which complete two-sided graphs work in the plane, and give extra rules for grid-like and tree-like cases.
Catalog record
| CREATOR | Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, Antonios Symvonis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-07361
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Geometric Realizations of Dichotomous Ordinal Graphs Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, Antonios Symvonis Abstract A dichotomous ordinal graph consists of an undirected graph with a partition of the edges into short and long edges. A geometric realization of a dichotomous ordinal graph G G in a metric space X X is a drawing of G G in X X in which every long edge is strictly longer than every short edge. We call a graph G G pandichotomous in X X if G G admits a geometric realization in X X for every partition of its edge set into short and long edges. We exhibit a very close relationship between the degeneracy of a graph G G and its pandichotomic Euclidean or spherical dimension , that is, the smallest dimension k k such that G G is pandichotomous in ℝ k \mathds{R}^{k} or the sphere 𝒮 k \mathcal{S}^{k} , respectively. First, every d d -degenerate graph is pandichotomous in ℝ d \mathds{R}^{d} and 𝒮 d − 1 \mathcal{S}^{d-1} and these bounds are tight for the sphere and for ℝ 2 \mathds{R}^{2} and almost tight for ℝ d \mathds{R}^{d} , for d ≥ 3 d\geq 3 . Second, every n n -vertex graph that is pandichotomous in ℝ k \mathds{R}^{k} has at most μ k n \mu kn edges, for some absolute constant μ < 7.23 \mu<7.23 . This shows that the pandichotomic Euclidean dimension of any graph is linearly tied to its degeneracy and in the special cases k ∈ { 1 , 2 } k\in\{1,2\} resolves open problems posed by Alam, Kobourov, Pupyrev, and Toeniskoetter. Further, we characterize which complete bipartite graphs are pandichotomous in ℝ 2 \mathds{R}^{2} : These are exactly the K m , n K_{m,n} with m ≤ 3 m\leq 3 or m = 4 m=4 and n ≤ 6 n\leq 6 . For general bipartite graphs, we can guarantee realizations in ℝ 2 \mathds{R}^{2} if the short or the long subgraph is constrained: namely if the short subgraph is outerplanar or a subgraph of a rectangular grid, or if the long subgraph forms a caterpillar. John Cabot University, Rome, [email protected]://orcid.org/0000-0002-7602-1524 University of Konstanz, [email protected]://orcid.org/0000-0002-1688-394X Trier University, [email protected]://orcid.org/0000-0001-6696-074X Department of Computer Science, ETH Zürich, Switzerland and https://people.inf.ethz.ch/hoffmann/ [email protected]://orcid.org/0000-0001-5307-7106 National Technical University of Athens, [email protected]://orcid.org/0000-0002-1001-1411 University of Perugia, [email protected]://orcid.org/0000-0002-0543-8912 ETH Zürich, [email protected]://orcid.org/0000-0002-4234-6136 National Technical University of Athens, [email protected]://orcid.org/0000-0002-0280-741X This work was initiated at the Annual Workshop on Graph and Network Visualization (GNV 2023), Chania, Greece, June 2023. ccs Mathematics of computing Combinatorics ccs Mathematics of computing Graph theory ccs Human-centered computing Graph drawings keywords Ordinal embeddings, geometric graphs, graph representations † † runningtitle: Geometric Realizations of Dichotomous Ordinal Graphs † † runningauthor: Angelini, Cornelsen, Haase, Hoffmann, Katsanou, Montecchiani, Steiner, Symvonis † † copyright: Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis † † editors: Oswin Aichholzer and Haitao Wang † † event-title: 41st International Symposium on Computational Geometry (SoCG 2025) † † event-shorttitle: SoCG 2025 † † event-acronym: SoCG † † year: 2025 † † event-date: June 23–27, 2025 † † event-location: Kanazawa, Japan † † event-logo: socg-logo.pdf † † series-volume: 332 † † articleno: XX 1 Introduction For an ordinal embedding , we are given a set of objects x_{1},\dots,x_{n} in an abstract space, together with a set of ordinal constraints of the form \mathrm{dist}(x_{i},x_{j})<\mathrm{dist}(x_{k},x_{\ell}) . The objective is to compute a set of points p_{1},\dots,p_{n} in a metric space while preserving as many ordinal constraints as possible. Ordinal embeddings were first studied in the 1960’s by Shepard [ 20 , 21 ] and Kruskal [ 13 , 14 ] in the context of psychometric data analysis. Recently, there have been applications in the field of Machine Learning [ 23 ] . The computation of ordinal embeddings is also known in the literature as non-metric multi-dimensional scaling. For an extensive literature review on ordinal embeddings refer to [ 24 ] . Of particular interest in relation to our work is the application of ordinal embeddings to the problem of recognizing multidimensional preferences [ 5 , 7 , 19 ] in the field of Computational Social Science. The objects are either voters or options , which, together with the ordinal constraints (i.e., the voters’ preferences), naturally define a bipartite graph. However, the goal is to find an embedding in \mathds{R}^{d} where all constraints are satisfied rather than to seek for an approximation. Efficient algorithms exist when d=1 [ 6 , 7 ] , while for any d\geq 2 the problem is as hard as the existential theory of the reals [ 19 ] . In the simplest case, the preferences form a dichotomy , that is, a voter may either support or reject an option [ 9 , 19 ] . This setting is naturally modeled as a dichotomous ordinal graph , which consists of an undirected graph G=(V,E_{s}\cup E_{\ell}) together with a partition of the edges into a set E_{s} of short edges and a set E_{\ell} of long edges. A geometric realization of a dichotomous ordinal graph G is a drawing \Gamma of G in some metric space along with a threshold \delta>0 such that the short edges of G are exactly those that have length at most \delta in \Gamma . In this work we consider two natural classes of drawings in which edges are drawn as geometrically shortest paths: (1) straight-line drawings in the Euclidean space \mathds{R}^{d} and (2) geodesic drawings on the sphere \mathcal{S}^{d} . Figure 1 shows two straight-line drawings of the same dichotomous ordinal graph in \mathds{R}^{2} . The drawing in (a) is a valid geometric realization, whereas the drawing in (b) is not. \subcaption valid drawing of \triangle uvw \subcaption invalid drawing of \triangle uvw Figure 1: A dichotomous ordinal triangle. Short edges are shown blue/solid, long edges red/dashed. A dichotomous ordinal graph may or may not be realizable in any particular space. For instance, it is easy to see that K_{4} where the short edges induce a star cannot be realized in \mathds{R}^{1} . In general, it is NP-hard to decide whether a dichotomous ordinal graph admits a geometric realization in \mathds{R}^{2} , even if the underlying graph is a complete graph and the short edges induce a planar graph [ 3 , Lemma 1] . According to Peters [ 19 , Theorem 4] the problem is \exists\mathds{R} -complete for bipartite graphs. 1 1 1 But even the full version of the paper [ 18 ] does not contain an explicit proof but only refers to the work of Kang and Müller [ 12 , Theorem 1] . The graph constructed in this proof is not bipartite. While it is plausible that the construction could be adapted, it does not seem immediately obvious to us. In light of the motivation, it is desirable that a geometric realization always exists, no matter the preferences of the voters. We call a graph G=(V,E) pandichotomous in a metric space X if G admits a geometric realization in X for every partition of E into short and long edges. Graphs that are pandichotomous in \mathds{R}^{1} are also called total-threshold-colorable [ 1 ,