Matching edges and faces in polygonal partitions

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 ex...

Full description

Saved in:
Bibliographic Details
Published in:Computational geometry : theory and applications 2008-02, Vol.39 (2), p.134-141
Main Authors: Aichholzer, O., Aurenhammer, F., Gonzalez-Nava, P., Hackl, T., Huemer, C., Hurtado, F., Krasser, H., Ray, S., Vogtenhuber, B.
Format: Article
Language:English
Subjects:
Laman condition
Perfect matching
Polygonal partition
Pseudo-triangulation
Quadrangulation
Tree decomposition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0925-7721
DOI:10.1016/j.comgeo.2007.07.002