Condizioni per il grafico bipartito per essere planare senza bordi che girano intorno ai vertici

Question

Un grafico bipartito è planar iff non ha $ k_ {3, 3} $ o $ k_5 $ minori.

Sto cercando condizioni necessarie o/e sufficienti per consentire i disegni planare senza bordi "che vanno in giro" di vertici. Questi sono disegni soddisfacenti:

1. Tutti i vertici di una parte sono disegnati su una singola linea verticale. I vertici dell'altra parte sono disegnati su una linea di verticelle parallele.
2. I bordi non si intersecano se non ai vertici.
3. I bordi sono tutti nella striscia infinita tra le due linee verticali al punto 1.

Ad esempio, tutti i disegni qui, tranne in basso a destra, non sono grandi. Il grafico in basso a sinistra può essere ridotto per soddisfare le condizioni scambiando le posizioni di Q e R. Le cime che due grafici non possono essere ridisegnati per soddisfare le condizioni.

I primi due grafici sono gli unici ostacoli che ho trovato. Le mie domande sono:

1. Questo problema ha un nome?
2. Qualche altro ostacolo che mi mancava?
3. Qualsiasi suggerimento su come posso dimostrare che questi due ostacoli (insieme a qualsiasi cosa mi mancasse), come minori, ovviamente, sono necessari e sufficienti.

Si noti che questo non è lo stesso che essere il piano esterno, $ k_ {2, 2} $ è esterno-piano (può essere disegnato come un quadrato) ma non può essere disegnato per soddisfare le condizioni che menzionisco sopra.