Intersection graphs of Jordan arcs | Zendy

Hubert de Fraysseix | Zendy; Patrice Ossona de Mendez | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Intersection graphs of Jordan arcs

Author(s) -

Hubert de Fraysseix,

Patrice Ossona de Mendez

Publication year - 1999

Publication title -

dimacs series in discrete mathematics and theoretical computer science

Language(s) - English

Resource type - Book series

eISSN - 2472-4793

pISSN - 1052-1798

DOI - 10.1090/dimacs/049/02

Subject(s) - intersection graph , intersection (aeronautics) , hypergraph , mathematics , combinatorics , simple (philosophy) , graph , tangent , representation (politics) , point (geometry) , discrete mathematics , line graph , geometry , geography , cartography , philosophy , epistemology , politics , political science , law

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research