On plane cycles in geometric multipartite graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918070006579200 |
|---|---|
| author | Ricci, Marco Rollin, Jonathan Schulz, André Weinberger, Alexandra |
| author_facet | Ricci, Marco Rollin, Jonathan Schulz, André Weinberger, Alexandra |
| contents | 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 \geq 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 \leq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_20421 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On plane cycles in geometric multipartite graphs Ricci, Marco Rollin, Jonathan Schulz, André Weinberger, Alexandra Computational Geometry Combinatorics 68R10 G.2.2 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 \geq 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 \leq 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. |
| title | On plane cycles in geometric multipartite graphs |
| topic | Computational Geometry Combinatorics 68R10 G.2.2 |
| url | https://arxiv.org/abs/2506.20421 |