Drawing outerplanar graphs using three edge lengths

Noga Alon; Ohad N. Feldheim

doi:10.1016/j.comgeo.2014.10.006

Drawing outerplanar graphs using three edge lengths

Noga Alon, Ohad N. Feldheim

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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 language	English (US)
Pages (from-to)	260-267
Number of pages	8
Journal	Computational Geometry: Theory and Applications
Volume	48
Issue number	3
DOIs	https://doi.org/10.1016/j.comgeo.2014.10.006
State	Published - Mar 2015
Externally published	Yes

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

Access to Document

10.1016/j.comgeo.2014.10.006

Cite this

@article{0619173551884fd4ae8909232d063216,

title = "Drawing outerplanar graphs using three edge lengths",

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{\'c}, Morin and Wood. The proof combines (elementary) geometric, combinatorial, algebraic and probabilistic arguments.",

keywords = "Degenerate drawing of a graph, Distance number of a graph, Outerplanar graphs",

author = "Noga Alon and Feldheim, \{Ohad N.\}",

year = "2015",

month = mar,

doi = "10.1016/j.comgeo.2014.10.006",

language = "English (US)",

volume = "48",

pages = "260--267",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Drawing outerplanar graphs using three edge lengths

AU - Alon, Noga

AU - Feldheim, Ohad N.

PY - 2015/3

Y1 - 2015/3

N2 - 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.

AB - 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.

KW - Degenerate drawing of a graph

KW - Distance number of a graph

KW - Outerplanar graphs

UR - https://www.scopus.com/pages/publications/84908428979

UR - https://www.scopus.com/inward/citedby.url?scp=84908428979&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2014.10.006

DO - 10.1016/j.comgeo.2014.10.006

M3 - Article

AN - SCOPUS:84908428979

SN - 0925-7721

VL - 48

SP - 260

EP - 267

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -

Drawing outerplanar graphs using three edge lengths

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this