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 \mathcal G be a family of planar graphs such that for each graph in the family |R| vertices are red and |B| vertices are blue. The set R ∪ B is a universal pointset for \mathcal G if every graph G \in \mathcal 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 pointsets for meaningful classes of 2-coloured trees and show applications of these results to the coloured simultaneous geometric embeddability problem.
Universal Pointsets for 2-Coloured Trees
LIOTTA, Giuseppe;
2011
Abstract
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 \mathcal G be a family of planar graphs such that for each graph in the family |R| vertices are red and |B| vertices are blue. The set R ∪ B is a universal pointset for \mathcal G if every graph G \in \mathcal 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 pointsets for meaningful classes of 2-coloured trees and show applications of these results to the coloured simultaneous geometric embeddability problem.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
