TY - JOUR
T1 - Matching edges and faces in polygonal partitions
AU - Aichholzer, O.
AU - Aurenhammer, F.
AU - Gonzalez-Nava, P.
AU - Hackl, T.
AU - Huemer, C.
AU - Hurtado, F.
AU - Krasser, H.
AU - Ray, S.
AU - Vogtenhuber, B.
N1 - Funding Information:
✩ Research partially supported by: FWF Joint Research Project Industrial Geometry S9205-N12, Projects MEC MTM2006-01267 and DURSI 2005SGR00692, Acción Intergrada España–Austria HU2002-0010, International-Max-Planck-School Saarbrücken. * Corresponding author. E-mail addresses: [email protected] (O. Aichholzer), [email protected] (F. Aurenhammer), [email protected] (P. Gonzalez-Nava), [email protected] (T. Hackl), [email protected] (C. Huemer), [email protected] (F. Hurtado), [email protected] (H. Krasser), [email protected] (S. Ray), [email protected] (B. Vogtenhuber).
PY - 2008/2
Y1 - 2008/2
N2 - 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.
AB - 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.
KW - Laman condition
KW - Perfect matching
KW - Polygonal partition
KW - Pseudo-triangulation
KW - Quadrangulation
KW - Tree decomposition
UR - http://www.scopus.com/inward/record.url?scp=84867925566&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867925566&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2007.07.002
DO - 10.1016/j.comgeo.2007.07.002
M3 - Article
AN - SCOPUS:84867925566
SN - 0925-7721
VL - 39
SP - 134
EP - 141
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 2
ER -