Matching edges and faces in polygonal partitions

O. Aichholzer, F. Aurenhammer, P. Gonzalez-Nava, T. Hackl, C. Huemer, F. Hurtado, H. Krassex, S. Ray, B. Vogtenhuber

Research output: Contribution to conferencePaperpeer-review


We define general Laman (count) conditions for edges and faces of polygonal partitions in the plane-Several well-known classes, including k-regular partitions, k-angulations, and rank-A; pseudo-triangulations, are shown to fulfill such conditions. As a consequence, non-trivial perfect matchings exist between the edge sets (or face sets) of two such structures when they live on the same point set. We also describe a link to spanning tree decompositions that applies to quadrangula-tions and certain pseudo-triangulations.

Original languageEnglish (US)
Number of pages4
StatePublished - 2005
Event17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada
Duration: Aug 10 2005Aug 12 2005


Conference17th Canadian Conference on Computational Geometry, CCCG 2005

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Matching edges and faces in polygonal partitions'. Together they form a unique fingerprint.

Cite this