1 Search Results for "Kaluža, Vojtech"

Document

DOI: 10.4230/LIPIcs.SoCG.2016.43

Shortest Path Embeddings of Graphs on Surfaces

Authors: Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding. The main question addressed in this paper is whether given a closed surface S, there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces. We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property. Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g, there exist graphs G embeddable into the orientable surface of genus g, such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G, where the probability measure is proportional to the Weil-Petersson volume on moduli space. Finally, we construct a hyperbolic metric on every orientable surface S of genus g, such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O(g) shortest paths.

Cite as

Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer. Shortest Path Embeddings of Graphs on Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hubard_et_al:LIPIcs.SoCG.2016.43,
  author =	{Hubard, Alfredo and Kalu\v{z}a, Vojtech and de Mesmay, Arnaud and Tancer, Martin},
  title =	{{Shortest Path Embeddings of Graphs on Surfaces}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.43},
  URN =		{urn:nbn:de:0030-drops-59356},
  doi =		{10.4230/LIPIcs.SoCG.2016.43},
  annote =	{Keywords: Graph embedding, surface, shortest path, crossing number, hyperbolic geometry}
}

Refine by Author
1 Hubard, Alfredo
1 Kaluža, Vojtech
1 Tancer, Martin
1 de Mesmay, Arnaud

Refine by Classification

Refine by Keyword
1 Graph embedding
1 crossing number
1 hyperbolic geometry
1 shortest path
1 surface

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Kaluža, Vojtech"

Shortest Path Embeddings of Graphs on Surfaces

Abstract

Cite as

Thanks for your feedback!

Could not send message