On Plane Cycles in Geometric Multipartite Graphs
摘要
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 \(\lceil t/2\rceil +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 + nk^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.