
586 CHAPTER 18. GDTOOLKIT
The first type of constraint imposes that an edge e is not allowed to cross any other edge.
If edge e is split into two edges e
1
and e
2
, the constraint is propagated on both e
1
and e
2
.
Symmetrically, if an edge e is obtained by merging two edges e
1
, e
2
, and at least one of
them is not crossable, then e will become not crossable too. If the planarization algorithm
encounters an edge e that is not crossable, it omits to insert its dual edge in the dual graph
of the planar embedded graph computed so far. This implies that a shortest path in the
dual graph never intersects e.
The second type of constraint imposes that a specified