Different Types of Isomorphisms of Drawings of Complete Multipartite Graphs

O. Aichholzer, B. Vogtenhuber, and A. Weinberger

Abstract:

Simple drawings are drawings of graphs in which any two edges intersect at most once (either at a common endpoint or a proper crossing), and no edge intersects itself. We analyze several characteristics of simple drawings of complete multipartite graphs: which pairs of edges cross, in which order they cross, and the cyclic order around vertices and crossings, respectively. We consider all possible combinations of how two drawings can share some characteristics and determine which other characteristics they imply and which they do not imply. Our main results are that for simple drawings of complete multipartite graphs, the orders in which edges cross determine all other considered characteristics. Further, if all partition classes have at least three vertices, then the pairs of edges that cross determine the rotation system and the rotation around the crossings determine the extended rotation system. We also show that most other implications - including the ones that hold for complete graphs - do not hold for complete multipartite graphs. Using this analysis, we establish which types of isomorphisms are meaningful for simple drawings of complete multipartite graphs.

Reference: O. Aichholzer, B. Vogtenhuber, and A. Weinberger. Different types of isomorphisms of drawings of complete multipartite graphs. In M. A. Bekos and M. Chimani, editors, Graph Drawing and Network Visualization, volume 14466 of Lecture Notes in Computer Science (LNCS), pages 34-50, Cham, 2023. Springer Nature Switzerland.