Intersection Graphs of Jordan Arcs
De Fraysseix, Hubert ; Ossona De Mendez, Patrice
HAL, hal-00005625 / Harvested from HAL
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.
Publié le : 1999-07-05
Classification:  graph drawing,  intersection representation,  05C62,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00005625,
     author = {De Fraysseix, Hubert and Ossona De Mendez, Patrice},
     title = {Intersection Graphs of Jordan Arcs},
     journal = {HAL},
     volume = {1999},
     number = {0},
     year = {1999},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00005625}
}
De Fraysseix, Hubert; Ossona De Mendez, Patrice. Intersection Graphs of Jordan Arcs. HAL, Tome 1999 (1999) no. 0, . http://gdmltest.u-ga.fr/item/hal-00005625/