On the Biplanarity of Blowups
The 2-blowup of a graph is obtained by replacing each vertex with two non-adjacent copies; a graph is biplanar if it is the union of two planar graphs. We disprove a conjecture of Gethner that 2-blowups of planar graphs are biplanar: iterated Kleetopes are counterexamples. Additionally, we construct biplanar drawings of 2-blowups of planar graphs whose duals have two-path induced path partitions, and drawings with split thickness two of 2-blowups of 3-chromatic planar graphs, and of graphs that can be decomposed into a Hamiltonian path and a dual Hamiltonian path.
Authors
- David Eppstein
Publication Details
- Journal
- Journal of Graph Algorithms and Applications
- Published
- 2024-10-28
- DOI
- https://doi.org/10.7155/jgaa.v28i2.2989
- Primary Topic
- Modeling, Simulation, and Optimization
- Type
- article
- Field-Weighted Citation Impact
- 0.00