198 Search Results for "Hoffmann, Michael"


Document
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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} 
}
  • Refine by Author
  • 178 dblp Team
  • 15 Hoffmann, Michael
  • 3 Erlebach, Thomas
  • 3 Kaufmann, Michael
  • 2 Chaplick, Steven
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 178 bibliography
  • 178 computer science
  • 178 dblp
  • 178 knowledge graph
  • 178 open data
  • Show More...

  • Refine by Type
  • 178 artifact
  • 20 document

  • Refine by Publication Year
  • 28 2023
  • 27 2022
  • 27 2024
  • 18 2021
  • 15 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail