2026-08-01T23:08:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23161 2025-10-02T12:41:33Z ddc:004 open_access

Geometric Realizations of Dichotomous Ordinal Graphs Angelini, Patrizio Cornelsen, Sabine Haase, Carolina Hoffmann, Michael Katsanou, Eleni Montecchiani, Fabrizio Steiner, Raphael Symvonis, Antonios Ordinal embeddings geometric graphs graph representations 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 in a metric space X is a drawing of G in X in which every long edge is strictly longer than every short edge. We call a graph G pandichotomous in X if G admits a geometric realization in 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 and its pandichotomic Euclidean or spherical dimension, that is, the smallest dimension k such that G is pandichotomous in ℝ^k or the sphere 𝒮^k, respectively. First, every d-degenerate graph is pandichotomous in ℝ^d and 𝒮^{d-1} and these bounds are tight for the sphere and for ℝ² and almost tight for ℝ^d, for d ≥ 3. Second, every n-vertex graph that is pandichotomous in ℝ^k has at most μ kn edges, for some absolute constant μ < 7.23. This shows that the pandichotomic Euclidean dimension of any graph is linearly tied to its degeneracy and in the special case k ∈ {1,2} resolves open problems posed by Alam, Kobourov, Pupyrev, and Toeniskoetter. Further, we characterize which complete bipartite graphs are pandichotomous in ℝ²: These are exactly the K_{m,n} with m ≤ 3 or m = 4 and n ≤ 6. For general bipartite graphs, we can guarantee realizations in ℝ² 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patrizio Angelini and Sabine Cornelsen and Carolina Haase and Michael Hoffmann and Eleni Katsanou and Fabrizio Montecchiani and Raphael Steiner and Antonios Symvonis 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.9 urn:nbn:de:0030-drops-231616 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode