๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On a straight-line embedding problem of graphs

โœ Scribed by Shin-ichi Tokunaga

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
372 KB
Volume
150
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane ~2 in general position. A straight-line embeddin9 of G onto P is an embedding of G onto R 2 whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p E P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.

๐Ÿ“œ SIMILAR VOLUMES

On the Number of Acute Triangles in a St
On the Number of Acute Triangles in a Straight-Line Embedding of a Maximal Planar Graph
โœ Atsushi Kaneko; Hiroshi Maehara; Mamoru Watanabe ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 80 KB

In this paper we show that any maximal planar graph with m triangles except the unbounded face can be transformed into a straight-line embedding in which at least Wmร‚3X triangles are acute triangles. Moreover, we show that any maximal outerplanar graph can be transformed into a straight-line embeddi

Straight line embeddings of cubic planar
Straight line embeddings of cubic planar graphs with integer edge lengths
โœ Jim Geelen; Anjie Guo; David McKinnon ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 87 KB

## Abstract We prove that every simple cubic planar graph admits a planar embedding such that each edge is embedded as a straight line segment of integer length. ยฉ 2008 Wiley Periodicals, Inc. J Graph Theory 58:270โ€274, 2008

On-line Planar Graph Embedding
On-line Planar Graph Embedding
โœ Roberto Tamassia ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 504 KB

We present a dynamic data structure for the incremental construction of a planar embedding of a planar graph. The data structure supports the following ลฝ . operations: i testing if a new edge can be added to the embedding without ลฝ . introducing crossing; and ii adding vertices and edges. The time c

On the intersection of edges of a geomet
On the intersection of edges of a geometric graph by straight lines
โœ N. Alon; M.A. Perles ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 969 KB

A geometric graph ( = gg) is a pair G = (V, E), where V is a finite set of points ( = vertices) in general position in the plane, and E is a set of open straight line segments ( = edges) whose endpoints are in V. G is a convex gg ( = egg) if V is the set of vertices of a convex polygon. For n 3 1, 0

A note on some embedding problems for or
A note on some embedding problems for oriented graphs
โœ Andrew Treglown ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 88 KB

We conjecture that every oriented graph G on n vertices with + (G), -(G) โ‰ฅ 5n / 12 contains the square of a Hamilton cycle. We also give a conjectural bound on the minimum semidegree which ensures a perfect packing of transitive triangles in an oriented graph. A link between Ramsey numbers and perfe