Representations by Contact and Intersection of Segments |
| |
| Authors: | Hubert de Fraysseix Patrice Ossona de Mendez |
| |
| Affiliation: | (1) Centre d'Analyse et de Mathematique Sociales, CNRS UMR 8557, Ecole des Hautes Etudes en Sciences Sociales, 54 Boulevard Raspail, 75006, Paris, France |
| |
| Abstract: | A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a contact family
of segments and points. We deduce that any four-connected three-colorable plane graph is the contact graph of a family of
segments and that any four-colored planar graph without an induced C4 using four colors is the intersection graph of a family of straight line segments. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
