DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.9

Geometric Realizations of Dichotomous Ordinal Graphs

Authors: Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

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 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.

Cite as

Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis. Geometric Realizations of Dichotomous Ordinal Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.SoCG.2025.9,
  author =	{Angelini, Patrizio and Cornelsen, Sabine and Haase, Carolina and Hoffmann, Michael and Katsanou, Eleni and Montecchiani, Fabrizio and Steiner, Raphael and Symvonis, Antonios},
  title =	{{Geometric Realizations of Dichotomous Ordinal Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.9},
  URN =		{urn:nbn:de:0030-drops-231616},
  doi =		{10.4230/LIPIcs.SoCG.2025.9},
  annote =	{Keywords: Ordinal embeddings, geometric graphs, graph representations}
}

Artifact

Dataset

DOI: 10.4230/dblp.rdf.ntriples.2025-06-01

dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of June 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of June 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-06-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of June 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-06-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-06-01},
    month     = {June},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.xml.2025-06-01

dblp computer science bibliography – Monthly Snapshot XML Release of June 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of June 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2025-06-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of June 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2025-06-01},
    url       = {https://doi.org/10.4230/dblp.xml.2025-06-01},
    month     = {June},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.xml.2025-05-02

dblp computer science bibliography – Monthly Snapshot XML Release of May 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of May 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2025-05-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of May 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2025-05-02},
    url       = {https://doi.org/10.4230/dblp.xml.2025-05-02},
    month     = {May},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.rdf.ntriples.2025-05-02

dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-05-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-05-02},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-05-02},
    month     = {May},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.xml.2025-04-01

dblp computer science bibliography – Monthly Snapshot XML Release of April 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of April 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2025-04-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of April 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2025-04-01},
    url       = {https://doi.org/10.4230/dblp.xml.2025-04-01},
    month     = {April},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.rdf.ntriples.2025-04-01

dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-04-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-04-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-04-01},
    month     = {April},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.xml.2025-03-01

dblp computer science bibliography – Monthly Snapshot XML Release of March 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of March 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2025-03-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of March 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2025-03-01},
    url       = {https://doi.org/10.4230/dblp.xml.2025-03-01},
    month     = {March},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.rdf.ntriples.2025-03-01

dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-03-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-03-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-03-01},
    month     = {March},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.rdf.ntriples.2025-02-02

dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-02-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-02-02},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-02-02},
    month     = {February},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.xml.2025-02-02

dblp computer science bibliography – Monthly Snapshot XML Release of February 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of February 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2025-02-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of February 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2025-02-02},
    url       = {https://doi.org/10.4230/dblp.xml.2025-02-02},
    month     = {February},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.rdf.ntriples.2025-01-02

dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-01-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-01-02},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-01-02},
    month     = {January},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.xml.2025-01-02

dblp computer science bibliography – Monthly Snapshot XML Release of January 2025

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of January 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2025-01-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of January 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2025-01-02},
    url       = {https://doi.org/10.4230/dblp.xml.2025-01-02},
    month     = {January},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.xml.2024-12-02

dblp computer science bibliography – Monthly Snapshot XML Release of December 2024

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of December 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2024-12-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of December 2024}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2024-12-02},
    url       = {https://doi.org/10.4230/dblp.xml.2024-12-02},
    month     = {December},
    year      = {2024},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

Artifact

Dataset

DOI: 10.4230/dblp.rdf.ntriples.2024-12-02

dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2024

Authors: dblp Team

Abstract

Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2024-12-02,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2024}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2024-12-02},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2024-12-02},
    month     = {December},
    year      = {2024},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}

198 Search Results for "Hoffmann, Michael"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message