### 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 language | English (US) |
---|---|

Title of host publication | Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers |

Pages | 260-271 |

Number of pages | 12 |

DOIs | |

State | Published - Feb 26 2013 |

Externally published | Yes |

Event | 20th International Symposium on Graph Drawing, GD 2012 - Redmond, WA, United States Duration: Sep 19 2012 → Sep 21 2012 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7704 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 20th International Symposium on Graph Drawing, GD 2012 |
---|---|

Country | United States |

City | Redmond, WA |

Period | 9/19/12 → 9/21/12 |

### Keywords

- graph drawing
- increasing-chord
- self-approaching

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

*Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers*(pp. 260-271). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7704 LNCS). https://doi.org/10.1007/978-3-642-36763-2_23