The Edge Rotation Graph |
| |
Authors: | Javier Cano José-Miguel Díaz-Báñez Clemens Huemer Jorge Urrutia |
| |
Institution: | 1. Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México, Mexico, Mexico 2. Departamento de Matemática Aplicada II, Universidad de Sevilla, Seville, Spain 3. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Barcelona, Spain 4. Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico, Mexico
|
| |
Abstract: | Let P be a set of n points on the plane in general position, n ≥ 3. The edge rotation graph ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ , such as its connectivity and diameter. We show that if the vertices of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ are not triangulations of P, then it is connected and has diameter O(n 2). We also show that the chromatic number of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|