Self-approaching graphs

Soroush Alamdari, Timothy M. Chan, Elyot Grant, Anna Lubiw, Vinayak Pathak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we introduce self-approaching graph drawings. A straight-line drawing of a graph is self-approaching if, for any origin vertex s and any destination vertex t, there is an st-path in the graph such that, for any point q on the path, as a point p moves continuously along the path from the origin to q, the Euclidean distance from p to q is always decreasing. This is a more stringent condition than a greedy drawing (where only the distance between vertices on the path and the destination vertex must decrease), and guarantees that the drawing is a 5.33-spanner. We study three topics: (1) recognizing self-approaching drawings; (2) constructing self-approaching drawings of a given graph; (3) constructing a self-approaching Steiner network connecting a given set of points. We show that: (1) there are efficient algorithms to test if a polygonal path is self-approaching in ℝ2 and ℝ3, but it is NP-hard to test if a given graph drawing in ℝ3 has a self-approaching uv-path; (2) we can characterize the trees that have self-approaching drawings; (3) for any given set of terminal points in the plane, we can find a linear sized network that has a self-approaching path between any ordered pair of terminals.

Original languageEnglish (US)
Title of host publicationGraph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers
Pages260-271
Number of pages12
DOIs
StatePublished - 2013
Externally publishedYes
Event20th International Symposium on Graph Drawing, GD 2012 - Redmond, WA, United States
Duration: Sep 19 2012Sep 21 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7704 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Symposium on Graph Drawing, GD 2012
Country/TerritoryUnited States
CityRedmond, WA
Period9/19/129/21/12

Keywords

  • graph drawing
  • increasing-chord
  • self-approaching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Self-approaching graphs'. Together they form a unique fingerprint.

Cite this