Metadata only
Author
Date
2023Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
A set $\mathcal{G}$ 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 \in \mathcal{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_2(n)$ planar graphs on $n$ vertices. This constitutes a double-exponential improvement over the previously best known bound of $O(n\cdot 4^{n/11})$ for the same problem by Goenka, Semnani and Yip. Using our method we also provide a computer-free proof that there exists a conflict collection of size $30$, improving upon the previously smallest known conflict collection of size $49$ 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(\log n)$ 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^6$ planar $n$-vertex graphs with no simultaneous embedding. Show more
Publication status
publishedExternal links
Book title
Graph Drawing and Network VisualizationJournal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerEvent
Subject
Planar graphs; Simultaneous embedding; Conflict collection; Probabilistic methodOrganisational unit
03672 - Steger, Angelika / Steger, Angelika
Related publications and datasets
Is new version of: https://doi.org/10.48550/ARXIV.2305.19186
More
Show all metadata
ETH Bibliography
yes
Altmetrics