首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Graphs of Triangulations and Perfect Matchings
Authors:ME Houle  F Hurtado  M Noy  E Rivera-Campo
Institution:1. National Institute of Informatics, Tokyo, Japan
2. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Espa?a
3. Departamento de Matemáticas, Universidad Autónoma Metropolitana-Iztapalapa, México
Abstract:Given a set P of points in general position in the plane, the graph of triangulations ></img>                              </span> of <em>P</em> has a vertex for every triangulation of <em>P</em>, and two of them are adjacent if they differ by a single edge exchange. We prove that the subgraph <span class= ></img>                              </span> of <span class= ></img>                              </span>, consisting of all triangulations of <em>P</em> that admit a perfect matching, is connected. A main tool in our proof is a result of independent interest, namely that the graph <span class= ></img>                              </span> that has as vertices the non-crossing perfect matchings of <em>P</em> and two of them are adjacent if their symmetric difference is a single non-crossing cycle, is also connected.</td>
	  </tr> 
	  <tr>
	   <td align=
Keywords:Triangulation  Perfect matching  Non-crossing
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号