The contribution of this paper is twofold. It presents a new approach to the matched drawability problem of pairs of planar graphs and provides three algorithms based on this approach for drawing the pairs outerplane-outerpillar, outerplane-wheel and wheel-wheel. Further, it initiates the study of the matched drawability of triples of planar graphs: It presents an algorithm to compute a matched drawing of a triple of cycles and an algorithm to compute a matched drawing of a caterpillar and two universal level planar graphs. The results extend previous work on the subject and relate to existing literature about simultaneous embeddability and universal level planarity.
Matched Drawability of Graph Pairs and of Graph Triples
GRILLI, LUCA;LIOTTA, Giuseppe;
2009
Abstract
The contribution of this paper is twofold. It presents a new approach to the matched drawability problem of pairs of planar graphs and provides three algorithms based on this approach for drawing the pairs outerplane-outerpillar, outerplane-wheel and wheel-wheel. Further, it initiates the study of the matched drawability of triples of planar graphs: It presents an algorithm to compute a matched drawing of a triple of cycles and an algorithm to compute a matched drawing of a caterpillar and two universal level planar graphs. The results extend previous work on the subject and relate to existing literature about simultaneous embeddability and universal level planarity.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
