Show simple item record

dc.contributor.author
Sharir, Micha
dc.contributor.author
Sheffer, Adam
dc.contributor.author
Welzl, Emo
dc.date.accessioned
2023-06-19T09:33:34Z
dc.date.available
2017-06-10T12:39:56Z
dc.date.available
2023-06-19T09:33:34Z
dc.date.issued
2012-06
dc.identifier.isbn
978-1-4503-1299-8
en_US
dc.identifier.other
10.1145/2261250.2261277
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/61715
dc.description.abstract
We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of N points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are O(1.8181N) for cycles and O(1.1067N) for matchings. These imply a new upper bound of O(54.543N) on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound O(68.664N)). Our analysis is based on a weighted variant of Kasteleyn's linear algebra technique.
en_US
dc.language.iso
en
en_US
dc.publisher
Association for Computing Machinery
en_US
dc.subject
Spanning cycles
en_US
dc.subject
Perfect matchings
en_US
dc.subject
Kasteleyn's technique
en_US
dc.subject
Triangulations
en_US
dc.title
Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique
en_US
dc.type
Conference Paper
dc.date.published
2012-06-17
ethz.book.title
SoCG '12: Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry
en_US
ethz.pages.start
189
en_US
ethz.pages.end
198
en_US
ethz.event
28th Annual Symposium on Computational Geometry (SCG 2012)
en_US
ethz.event.location
Chapel Hill, NC, USA
en_US
ethz.event.date
June 17-20, 2012
en_US
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
ethz.date.deposited
2017-06-10T12:40:42Z
ethz.source
ECIT
ethz.identifier.importid
imp5936503918ae753386
ethz.ecitpid
pub:98197
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-12T17:40:29Z
ethz.rosetta.lastUpdated
2024-02-03T00:16:13Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Counting%20Plane%20Graphs:%20Perfect%20Matchings,%20Spanning%20Cycles,%20and%20Kasteleyn's%20Technique&rft.date=2012-06&rft.spage=189&rft.epage=198&rft.au=Sharir,%20Micha&Sheffer,%20Adam&Welzl,%20Emo&rft.isbn=978-1-4503-1299-8&rft.genre=proceeding&rft_id=info:doi/10.1145/2261250.2261277&rft.btitle=SoCG%20'12:%20Proceedings%20of%20the%20Twenty-Eighth%20Annual%20Symposium%20on%20Computational%20Geometry
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record