We show that planarity testing can be interpreted as a train switching problem. Train switching problems have been studied in the context of permutation networks, i.e., permuting the cars of a train on a given railroad network. The cars enter the network one at a time, some are stored temporarily in the network and the cars leave the network in the prescribed permutation.
展开▼
