Contractible edges in convex graphs

Ferran.Hurtado and Eduardo Rivera-Campo
Rényi Institute, Budapest and Courant Institute, New York, USA

Abstract

A convex graph is a 2-connected plane graph such that every face is bounded by a convex polygon.
Let u be an interior vertex of a convex graph G. An edge e=uv of G is contractible from u to v if we can move the vertex u into the vertex v (together with its incident edges) along the edge e in such a way that, at each stage, the corresponding graph is a convex graph.
In this note, we prove that every convex graph with at least one interior vertex contains a contractible edge.