Abstract | ||
---|---|---|
In this paper, 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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-319-13075-0_10 | ALGORITHMS AND COMPUTATION, ISAAC 2014 |
Keywords | DocType | Volume |
Planar matchings,Pseudo-line arrangements,Stable roommates,Weighted straight skeletons | Conference | 8889 |
Issue | ISSN | Citations |
3-4 | 0302-9743 | 1 |
PageRank | References | Authors |
0.39 | 7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Therese Biedl | 1 | 902 | 106.36 |
Stefan Huber | 2 | 24 | 3.38 |
Peter Palfrader | 3 | 17 | 5.57 |