TY - GEN
T1 - Different Types of Isomorphisms of Drawings of Complete Multipartite Graphs
AU - Aichholzer, Oswin
AU - Vogtenhuber, Birgit
AU - Weinberger, Alexandra
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Complete multipartite graphs
KW - Isomorphisms
KW - Simple Drawings
UR - https://www.scopus.com/pages/publications/85182590592
U2 - 10.1007/978-3-031-49275-4_3
DO - 10.1007/978-3-031-49275-4_3
M3 - Conference paper
AN - SCOPUS:85182590592
SN - 9783031492747
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 34
EP - 50
BT - Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers
A2 - Bekos, Michael A.
A2 - Chimani, Markus
PB - Springer Science and Business Media Deutschland GmbH
T2 - 31st International Symposium on Graph Drawing and Network Visualization
Y2 - 20 September 2023 through 22 September 2023
ER -