Drawing outerplanar graphs using three edge lengths

DOI10.1016/J.COMGEO.2014.10.006MaRDI QIDQ482350zbMATH OpenOpenAlexFDO

Authors Noga Alon, Ohad Noy Feldheim

Publication date 23 December 2014

Published in Computational Geometry (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 2145235 (Why is no real title available?)
• scientific article; zbMATH DE number 3893918 (Why is no real title available?)
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Distinct distances in graph drawings
• On Sets of Distances of n Points

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)