A pair of trees without a simultaneous geometric embedding in the plane
Abstract
Description
Any planar graph has a crossing-free straight-line drawing in the plane. A simultaneous geometric embedding of two n-vertex graphs is a straight-line drawing of both graphs on a common set of n points, such that the edges withing each individual graph do not cross. We consider simultaneous embeddings of two labeled trees, with predescribed vertex correspondences, and present an instance of such a pair that cannot be embedded. Further we provide an example of a planar graph that cannot be embedded together with a path when vertex correspondences are given.
This paper has been withdrawn by the author because it had turned out that the result was already known before
This paper has been withdrawn by the author because it had turned out that the result was already known before