On triconnected and cubic plane graphs on given point sets |
| |
| Authors: | Alfredo Garcí a, Ferran Hurtado, Clemens Huemer, Javier Tejel,Pavel Valtr |
| |
| Affiliation: | 1. Departamento de Métodos Estadísticos, Facultad de Ciencias, Universidad de Zaragoza, Pedro Cerbuna, 12, 50009 Zaragoza, Spain;2. Dept. Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain;3. Dept. Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Avinguda del Canal Olímpic 15, 08860 Castelldefels, Spain;4. Department of Applied Mathematics and Institute for Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic |
| |
| Abstract: | Let S be a set of n 4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{ 3n/2 ,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and h n/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph. |
| |
| Keywords: | Geometric graph Plane graph 3-connected graph Cubic graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
