Theory of multiplace graphs

Multiplace graphs are defined set-theoretically by the extension of binary relations in well-known graphs to multiplace relations. They are shown to give a sparse representation of bipartite graphs. Its usefulness is demonstrated by the planarization of graphs based on a new planarity theorem. Applications are especially in the circuit layout field.