Contact and Intersection Representations

De Fraysseix, Hubert and Ossona de Mendez, Patrice (2004) Contact and Intersection Representations. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 217-227(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_23).

Full text not available from this repository.

Abstract

A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a family of segments and points. We deduce that any 4-connected 3-colorable plane graph is the contact graph of a family of segments and that any 4-colored planar graph without an induced C_4 using 4 colors is the intersection graph of a family of straight line segments.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_23
Classifications: Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/589

Actions (login required)

View Item View Item