Show simple item record

dc.contributor.author
Steiner, Raphael
dc.date.accessioned
2024-06-11T14:45:25Z
dc.date.available
2024-06-11T05:22:49Z
dc.date.available
2024-06-11T14:45:25Z
dc.date.issued
2024
dc.identifier.issn
0179-5376
dc.identifier.issn
1432-0444
dc.identifier.other
10.1007/s00454-024-00665-7
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/677588
dc.identifier.doi
10.3929/ethz-b-000677588
dc.description.abstract
A set of planar graphs on the same number n of vertices is called simultaneously embeddable if there exists a set P of n points in the plane such that every graph G ∈ G admits a (crossing-free) straight-line embedding with vertices placed at points of P. A conflict collection is a set of planar graphs of the same order with no simultaneous embedding. A well-known open problem from 2007 posed by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw and Mitchell, asks whether there exists a conflict collection of size 2. While this remains widely open, we give a short proof that for sufficiently large n there exists a conflict collection consisting of at most (3 + o(1)) log₂(n) planar graphs on n vertices. This constitutes a double-exponential improvement over the previously best known bound of O(n · 4ⁿ/¹¹) for the same problem by Goenka et al. (Graphs Combin 39:100, 2023). Using our method we also provide a computer-free proof that for every integer n ∈ [107, 193] there exists a conflict collection of 30 planar n-vertex graphs, improving upon the previously smallest known conflict collection consisting of 49 graphs of order 11, which was found using heavy computer assistance. While the construction by Goenka et al. was explicit, our construction of a conflict collection of size O(logn) is based on the probabilistic method and is thus only implicit. Motivated by this, for every large enough n we give a different, fully explicit construction of a collection of less than n⁶ planar n-vertex graphs with no simultaneous embedding.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.subject
Planar graphs
en_US
dc.subject
Straight-line drawing
en_US
dc.subject
Simultaneous embedding
en_US
dc.subject
Conflict collection
en_US
dc.subject
Universal point set
en_US
dc.title
A Logarithmic Bound for Simultaneous Embeddings of Planar Graphs
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2024-06-04
ethz.journal.title
Discrete & Computational Geometry
ethz.journal.abbreviated
Discrete comput. geom.
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.wos
ethz.publication.status
published
en_US
ethz.date.deposited
2024-06-11T05:22:53Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.exportRequired
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=A%20Logarithmic%20Bound%20for%20Simultaneous%20Embeddings%20of%20Planar%20Graphs&rft.jtitle=Discrete%20&%20Computational%20Geometry&rft.date=2024&rft.issn=0179-5376&1432-0444&rft.au=Steiner,%20Raphael&rft.genre=article&rft_id=info:doi/10.1007/s00454-024-00665-7&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record