Drawing outerplanar graphs using three edge lengths

Noga Alon, Ohad N. Feldheim

Research output: Contribution to journalArticle

Abstract

It is shown that for any outerplanar graph G there is a one to one mapping of the vertices of G to the plane, so that the number of distinct distances between pairs of connected vertices is at most three. This settles a problem of Carmi, Dujmović, Morin and Wood. The proof combines (elementary) geometric, combinatorial, algebraic and probabilistic arguments.

Original languageEnglish (US)
Pages (from-to)260-267
Number of pages8
JournalComputational Geometry: Theory and Applications
Volume48
Issue number3
DOIs
StatePublished - Mar 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Degenerate drawing of a graph
  • Distance number of a graph
  • Outerplanar graphs

Fingerprint Dive into the research topics of 'Drawing outerplanar graphs using three edge lengths'. Together they form a unique fingerprint.

  • Cite this