Planar matchings for weighted straight skeletons

Biedl, Therese and Huber, Stefan G and Palfrader, Peter (2016) Planar matchings for weighted straight skeletons. International Journal of Computational Geometry and Applications, 26 (3-4). 211-229 . ISSN 1793-6357

[img] Text
2016_huber_PLanar_matchings.pdf - Published Version
Available under License Creative Commons Attribution.
Download (751Kb)
Official URL:


We introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist. Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings.

Item Type: Article
DOI: 10.1142/S0218195916600050
Uncontrolled Keywords: Planar matchings, pseudo-line arrangements, stable roommates, weighted straight skeletons
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
500 Science > 510 Mathematics > 514 Topology
500 Science > 510 Mathematics > 516 Geometry
Research Group: Edelsbrunner Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 29 Jan 2018 09:09
Last Modified: 29 Jan 2018 09:09

Actions (login required)

View Item View Item