Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 49-65
Citer cet article
D. V. Karpov. On plane drawings of $2$-planar graphs. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 49-65. http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a2/
@article{ZNSL_2019_488_a2,
author = {D. V. Karpov},
title = {On plane drawings of $2$-planar graphs},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {49--65},
year = {2019},
volume = {488},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a2/}
}
TY - JOUR
AU - D. V. Karpov
TI - On plane drawings of $2$-planar graphs
JO - Zapiski Nauchnykh Seminarov POMI
PY - 2019
SP - 49
EP - 65
VL - 488
UR - http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a2/
LA - ru
ID - ZNSL_2019_488_a2
ER -
%0 Journal Article
%A D. V. Karpov
%T On plane drawings of $2$-planar graphs
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 49-65
%V 488
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a2/
%G ru
%F ZNSL_2019_488_a2
It is proved that any $(2k+1)$-edge connected $k$-planar graph has a plane drawing such that any two crossing edges in this drawing cross each other exactly once. It is proved that any $2$-planar graph has a plane drawing such that any two crossing edges in this drawing has no common end and cross each other exactly once. It is also proved that any $2$-planar graph has a supergraph on the same vertex set which can be drawn such that, for any vertex $v$, among every three successive edges incident to $v$, there is at least one simple edge. (An edge is called simple if it does not intersect any other edge in this drawing).
[1] K. Wagner, “Bemerkungen zum Vierfarbenproblem”, Jahresbericht der Deutschen Mathematiker-Vereinigung, 46 (1936), 26–32
[2] I. Fáry, “On straight-line representation of planar graphs”, Acta Sci. Math. (Szeged), 11 (1948), 229–233 | MR | Zbl
[3] G. Ringel, “Ein Sechsfarbenproblem auf der Kugel”, Abhandlungen aus dem Mathematischen Seminar der Universităt Hamburg, 29 (1965), 107–117 | DOI | MR | Zbl
[4] J. Pach, G. Tóth, “Graphs drawn with few crossing per edge”, Combinatorica, 17:3 (1997), 427–439 | DOI | MR | Zbl
[5] O. V. Borodin, “Reshenie zadachi Ringelya o vershinno-granevoi raskraske ploskikh grafov i o raskraske 1-planarnykh grafov”, Metody diskretnogo analiza v izuchenii realizatsii logicheskikh funktsii, 41, Institut matematiki SO AN SSSR, Novosibirsk, 1984, 12–26