Matching Extension Missing Vertices and Edges in Triangulations of Surfaces |
| |
| Authors: | Ken‐ichi Kawarabayashi Kenta Ozeki Michael D. Plummer |
| |
| Affiliation: | 1. NATIONAL INSTITUTE OF INFORMATICS, CHIYODA‐KU, JAPAN;2. JST, ERATO, KAWARABAYASHI LARGE GRAPH PROJECT, JAPAN;3. DEPARTMENT OF MATHEMATICS, VANDERBILT UNIVERSITY, NASHVILLE, TN |
| |
| Abstract: | Let G be a 5‐connected triangulation of a surface Σ different from the sphere, and let  be the Euler characteristic of Σ. Suppose that  with  even and M and N are two matchings in  of sizes m and n respectively such that  . It is shown that if the pairwise distance between any two elements of  is at least five and the face‐width of the embedding of G in Σ is at least  , then there is a perfect matching M0 in  containing M such that  . |
| |
| Keywords: | triangulation matching extension representativity face‐width genus |
|
|
be the Euler characteristic of Σ. Suppose that 
with 
even and M and N are two matchings in 
of sizes m and n respectively such that 
. It is shown that if the pairwise distance between any two elements of 
is at least five and the face‐width of the embedding of G in Σ is at least 
, then there is a perfect matching M0 in 
containing M such that 
.