Universal point sets for 2-coloured trees
Let R and B be two sets of distinct points such that the points of R are coloured red and the points of B are coloured blue. Let G be a family of planar graphs such that for each graph in the family vertical bar R vertical bar vertices are red and vertical bar B vertical bar vertices are blue. The set R boolean OR B is a universal point set for G if every graph G is an element of g has a straight-line planar drawing such that the blue vertices of G are mapped to the points of B and the red vertices of G are mapped to the points of R. In this paper we describe universal point sets for meaningful classes of 2-coloured trees and show applications of these results to the coloured simultaneous geometric embeddability problem. (C) 2012 Elsevier B.V. All rights reserved.
universal point sets graph drawing coloured simultaneous embeddability computational geometry