On plane cycles in geometric multipartite graphs

Abstract

A geometric graph is a drawing of a graph in the plane where the vertices are drawn as points in general position and the edges as straight-line segments connecting their endpoints. It is plane if it contains no crossing edges. We study plane cycles in geometric complete multipartite graphs. We prove that if a geometric complete multipartite graph contains a plane cycle of length $t$, with $t\ge 6$, it also contains a smaller plane cycle of length at least $\lfloor t/2\rfloor +1$. We further give a characterization of geometric complete multipartite graphs that contain plane cycles with a color class appearing at least twice. For geometric drawings of $K_{n,n}$, we give a sufficient condition under which they have, for each $s\le n$, a plane cycle of length 2s. We also provide an algorithm to decide whether a given geometric drawing of $K_{n,n}$ contains a plane Hamiltonian cycle in time $O(n\log n+n{k}^2)+O(k^{5k})$, where k is the number of vertices inside the convex hull of all vertices. Finally, we prove that it is NP-complete to decide if a subset of edges of a geometric complete bipartite graph H is contained in a plane Hamiltonian cycle in H.

Appears in the proceedings of the 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG2025)