View Related Documents

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.

Fulltext Preview

Image of the first page of the fulltext document