Drawing outerplanar graphs using three edge lengths

DOI10.1016/J.COMGEO.2014.10.006zbMATH Open1305.05156arXiv1208.0744OpenAlexW3101983524MaRDI QIDQ482350FDOQ482350

Authors: Noga Alon, Ohad Noy Feldheim 

Publication date: 23 December 2014

Published in: Computational Geometry (Search for Journal in Brave)

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, Dujmovic, Morin and Wood. The proof combines (elementary) geometric, combinatorial, algebraic and probabilistic arguments.

Full work available at URL: https://arxiv.org/abs/1208.0744

Recommendations

• Drawing outerplanar graphs using thirteen edge lengths
• Degenerate drawing of outerplanar graphs with two edge lengths
• Graph Drawing
• Drawing outer-1-planar graphs revisited
• Drawing outer-1-planar graphs revisited
• Three-dimensional graph drawing
• Computing and Combinatorics
• Three-dimensional orthogonal graph drawing algorithms
• Convex drawings of 3-connected plane graphs
• Graph Drawing

zbMATH Keywords

outerplanar graphsdegenerate drawing of a graphdistance number of a graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On Sets of Distances of n Points
• Title not available (Why is that?)
• Distinct distances in graph drawings
• Title not available (Why is that?)

Cited In (8)

• Degenerate drawing of outerplanar graphs with two edge lengths
• A linear-time algorithm for testing outer-1-planarity
• Testing the planar straight-line realizability of 2-trees with prescribed edge lengths
• Graph Drawing
• Drawing outerplanar graphs using thirteen edge lengths
• Distinct distances in graph drawings
• Drawing Kn in Three Dimensions with One Bend per Edge
• Planar straight-line realizations of 2-trees with prescribed edge lengths

This page was built for publication: Drawing outerplanar graphs using three edge lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482350)