Matching edges and faces in polygonal partitions

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

Research output: Contribution to journalArticlepeer-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-k pseudo-triangulations, are shown to fulfill such conditions. As an implication, 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 quadrangulations and certain pseudo-triangulations.

Original languageEnglish (US)
Pages (from-to)134-141
Number of pages8
JournalComputational Geometry: Theory and Applications
Issue number2
StatePublished - Feb 2008


  • Laman condition
  • Perfect matching
  • Polygonal partition
  • Pseudo-triangulation
  • Quadrangulation
  • Tree decomposition

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


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

Cite this