Intersection Graphs of Jordan Arcs

De Fraysseix, Hubert and Ossona de Mendez, Patrice (1999) Intersection Graphs of Jordan Arcs. [In Collection]

Full text not available from this repository.

Abstract

A family of Jordan arcs, such that two arcs are nowhere tangent, defines a hypergraph whose vertices are the arcs and whose edges are the intersection points. We shall say that the hypergraph has a strong intersection representation and, if each intersection point is interior to at most one arc, we shall say that the hypergraph has a strong contact representation. We first characterize those hypergraphs which have a strong contact representation and deduce some sufficient conditions for a simple planar graph to have a strong intersection representation. Then, using the Four Color Theorem, we prove that a large class of simple planar graphs have a strong intersection representation.

Item Type:In Collection
Classifications:Z Theory > Z.500 Representations
ID Code:672

Repository Staff Only: item control page