Geodesic
On the Biplanarity of Blowups
David Eppstein1
1 University of California
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023 , Tome 28 (2024) no. 2, pp. 83-99.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.v28i2.2989
Keywords: Graph thickness, Split thickness, Graph blowups, Kleetopes

David Eppstein 1

1 University of California 
@article{JGAA_2024_28_2_a4,
     author = {David Eppstein},
     title = {On the {Biplanarity} of {Blowups}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {83--99},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2024},
     doi = {10.7155/jgaa.v28i2.2989},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2989/}
}
TY  - JOUR
AU  - David Eppstein
TI  - On the Biplanarity of Blowups
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 83
EP  - 99
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2989/
DO  - 10.7155/jgaa.v28i2.2989
LA  - en
ID  - JGAA_2024_28_2_a4
ER  - 
%0 Journal Article
%A David Eppstein
%T On the Biplanarity of Blowups
%J Journal of Graph Algorithms and Applications
%D 2024
%P 83-99
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2989/
%R 10.7155/jgaa.v28i2.2989
%G en
%F JGAA_2024_28_2_a4
David Eppstein. On the Biplanarity of Blowups. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirty-first International Symposium on Graph Drawing and Network Visualization, GD 2023
					, Tome 28 (2024) no. 2, pp. 83-99. doi : 10.7155/jgaa.v28i2.2989. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i2.2989/

Cité par Sources :