✦ LIBER ✦

Note on Geometric Graphs

✍ Scribed by Géza Tóth

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 206 KB
Volume: 89
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1999.3001

No coin nor oath required. For personal study only.

✦ Synopsis

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and the edges are represented by straight line segments connecting the corresponding points. We show that a geometric graph of n vertices with no k+1 pairwise disjoint edges has at most 2 9 k 2 n edges.

📜 SIMILAR VOLUMES

Note on projective graphs

✍ Tomasz Łuczak; Jaroslav Nešetřil 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 69 KB

## Abstract We show that all graphs with a simple extension property are projective. As a consequence of this result we settle in the affirmative a conjecture of Larose and Tardif and characterize all homogeneous graphs which are projective. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 81–86,

Distinguishing geometric graphs

✍ Michael O. Albertson; Debra L. Boutin 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 196 KB

## Abstract We begin the study of distinguishing geometric graphs. Let __G__ be a geometric graph. An automorphism of the underlying graph that preserves both crossings and noncrossings is called a __geometric automorphism__. A labeling, __f__: __V__(__G__) → {1, 2, … , __r__}, is said to be __r‐di

Approximating Layout Problems on Random

Approximating Layout Problems on Random Geometric Graphs

✍ Josep Dı́az; Mathew D. Penrose; Jordi Petit; Marı́a Serna 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 308 KB

In this paper, we study the approximability of several layout problems on a family of random geometric graphs. Vertices of random geometric graphs are randomly distributed on the unit square and are connected by edges whenever they are closer than some given parameter. The layout problems that we co

Geometric graph homomorphisms

✍ Debra L. Boutin; Sally Cockburn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract A __geometric graph__ is a simple graph drawn on points in the plane, in general position, with straightline edges. A __geometric__ __homomorphism__ from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th