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

doi:10.1016/j.comgeo.2007.07.002

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

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	134-141
Number of pages	8
Journal	Computational Geometry: Theory and Applications
Volume	39
Issue number	2
DOIs	https://doi.org/10.1016/j.comgeo.2007.07.002
State	Published - Feb 2008

Keywords

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

Access to Document

10.1016/j.comgeo.2007.07.002

Cite this

@article{8b2e1c97cc8a49dc8fa5853e03e41bf6,

title = "Matching edges and faces in polygonal partitions",

abstract = "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.",

keywords = "Laman condition, Perfect matching, Polygonal partition, Pseudo-triangulation, Quadrangulation, Tree decomposition",

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

note = "Funding Information: ✩ Research partially supported by: FWF Joint Research Project Industrial Geometry S9205-N12, Projects MEC MTM2006-01267 and DURSI 2005SGR00692, Acci{\'o}n Intergrada Espa{\~n}a–Austria HU2002-0010, International-Max-Planck-School Saarbr{\"u}cken. * Corresponding author. E-mail addresses: oaich@ist.tugraz.at (O. Aichholzer), auren@igi.tugraz.at (F. Aurenhammer), paolag@sbox.tugraz.at (P. Gonzalez-Nava), thackl@ist.tugraz.at (T. Hackl), Huemer.Clemens@upc.edu (C. Huemer), Ferran.Hurtado@upc.edu (F. Hurtado), hkrasser@igi.tugraz.at (H. Krasser), saurabh@mpi-sb.mpg.de (S. Ray), bvogt@ist.tugraz.at (B. Vogtenhuber).",

year = "2008",

month = feb,

doi = "10.1016/j.comgeo.2007.07.002",

language = "English (US)",

volume = "39",

pages = "134--141",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "2",

}

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: oaich@ist.tugraz.at (O. Aichholzer), auren@igi.tugraz.at (F. Aurenhammer), paolag@sbox.tugraz.at (P. Gonzalez-Nava), thackl@ist.tugraz.at (T. Hackl), Huemer.Clemens@upc.edu (C. Huemer), Ferran.Hurtado@upc.edu (F. Hurtado), hkrasser@igi.tugraz.at (H. Krasser), saurabh@mpi-sb.mpg.de (S. Ray), bvogt@ist.tugraz.at (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 -

Matching edges and faces in polygonal partitions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this