DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.13

Algorithms for Distance Problems in Continuous Graphs

Authors: Sergio Cabello, Delia Garijo, Antonia Kalb, Fabian Klute, Irene Parada, and Rodrigo I. Silveira

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with m edges these values can be computed in roughly O(m²) time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most k can be computed in O(n log^O(k) n) time, where n is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with n vertices and F faces takes O(n F log n) time.

Cite as

Sergio Cabello, Delia Garijo, Antonia Kalb, Fabian Klute, Irene Parada, and Rodrigo I. Silveira. Algorithms for Distance Problems in Continuous Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.WADS.2025.13,
  author =	{Cabello, Sergio and Garijo, Delia and Kalb, Antonia and Klute, Fabian and Parada, Irene and Silveira, Rodrigo I.},
  title =	{{Algorithms for Distance Problems in Continuous Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.13},
  URN =		{urn:nbn:de:0030-drops-242446},
  doi =		{10.4230/LIPIcs.WADS.2025.13},
  annote =	{Keywords: diameter, mean distance, continuous graph, treewidth, planar graph}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.15

Computing Optimal Shortcuts for Networks

Authors: Delia Garijo, Alberto Márquez, Natalia Rodríguez, and Rodrigo I. Silveira

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Questions of this type have received considerable attention recently, mostly for discrete variants of the problem. We study a fully continuous setting, where all points on the network and the inserted segment must be taken into account. We present the first results on the computation of optimal shortcuts for general networks in this model, together with several results for networks that are paths, restricted to two types of shortcuts: shortcuts with a fixed orientation and simple shortcuts.

Cite as

Delia Garijo, Alberto Márquez, Natalia Rodríguez, and Rodrigo I. Silveira. Computing Optimal Shortcuts for Networks. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{garijo_et_al:LIPIcs.ISAAC.2018.15,
  author =	{Garijo, Delia and M\'{a}rquez, Alberto and Rodr{\'\i}guez, Natalia and Silveira, Rodrigo I.},
  title =	{{Computing Optimal Shortcuts for Networks}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{15:1--15:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.15},
  URN =		{urn:nbn:de:0030-drops-99634},
  doi =		{10.4230/LIPIcs.ISAAC.2018.15},
  annote =	{Keywords: graph augmentation, shortcut, diameter, geometric graph}
}

Search Results

Documents authored by Garijo, Delia

Algorithms for Distance Problems in Continuous Graphs

Abstract

Cite as

Computing Optimal Shortcuts for Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message