# Definition: Interlacing Pieces with Respect to a Cycle, Interlacement Graph

Let $$G(V,E,\gamma)$$ be an biconnected graph and let $$C(V_c,E_c)$$ be a cycle in $$G$$1, such that the cycle $$C$$ (but not necessarily the whole graph $$G$$) has2 a planar drawing so that the planar drawing of $$C$$ divides the plane into an interior region bounded by the drawing and an exterior region3.

### Example

In the following figure a drawing of a graph $$G$$ is shown, which is not planar, however, the cycle $$C$$ (blue) has a planar drawing:

We say that two pieces of $$G$$ with respect to $$C$$ interlace, if they can neither be drawn entirely in the interior of $$C$$ nor can they be drawn entirely in the exterior of $$C$$, without violating planarity.

In our example, there are $$6$$ pieces of $$G$$ with respect to $$C$$. In particular, the pieces $$P_2$$ and $$P_1$$ interlace, while the the pieces $$P_2$$ and $$P_3$$ do not interlace:

The interlacement graph $$I(V_i,E_i)$$ of the pieces of $$G$$ with respect to $$C$$ is the graph whose vertices $$V_i$$ are the pieces of $$G$$ and whose edges $$E_i$$ are the pairs of pieces that interlace.

The following figure demonstrates the interlacement graph of our example:

Theorems: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Di Battista G., Eades P., Tamassia R., Tollis, I.G.: "Graph Drawing - Algorithms for the Visualization of Graphs", Prentice-Hall, Inc., 1999

#### Footnotes

1. Please note that in a biconnected graph such a cycle always exists.

2. Please note that every cycle has a planar drawing. The condition requiring $$C$$ to have a planar drawing is made in this definition only for the reason to make sure that an interior and exterior of the drawing of $$C$$ exists.

3. The existence of an interior and an exterior region follows from the Jordan Curve Theorem (still to be done at BookOfProofs).