RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2019 Volume 488, Pages 49–65 (Mi znsl6912)

This article is cited in 1 paper

On plane drawings of $2$-planar graphs

D. V. Karpovab

a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences
b Saint Petersburg State University

Abstract: 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).

Key words and phrases: $2$-planar graph, plane drawing of a graph.

UDC: 519.173.2

Received: 05.12.2019



© Steklov Math. Inst. of RAS, 2024