Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 07/2012

ВЕРХНЯЯ ОЦЕНКА КОЛИЧЕСТВА РЕБЕР В ДВУДОЛЬНОМ ПОЧТИ ПЛАНАРНОМ ГРАФЕ

This preprint was accepted March 21, 2012

АННОТАЦИЯ:
Пусть $G$ --- двудольный граф без петель и кратных рёбер на $v\ge 4$ вершинах, 
который можно изобразить на плоскости так, чтобы каждое ребро пересекало не более, 
чем одно другое. В работе доказывается, что при чётном $v\ne 6$ в таком графе 
не более чем $3v-8$ рёбер, а при нечетном $v$  и $v=6$ --- не более чем $3v-9$ рёбер. 
Для всех $v\ge 4$ построены примеры графов, для которых эти оценки достигаются.

В конце работы мы обсудим вопрос об изображении на плоскости полных двудольных графов 
не более чем с одним пересечением на каждом ребре.

 ©

D. V. KARPOV

UPPER BOUND ON THE NUMBER OF EDGES IN BIPARTITE ALMOST PLANAR GRAPH

ABSTRACT:
Let $G$ be a bipartite graph without loops and multiple edges on $v\ge 4$ vertices, 
which can be drawn in the plane such that every edge crosses at most one edge.
We prove that  the number of edges of the graph $G$ does not exceed $3v-8$ for
even~$v\ne 6$ and does not exceed $3v-9$ for odd  $v$  and $v=6$.
 We construct  graphs for which our bound is attained for each $v\ge 4$.

In the end of the paper we discuss the question about drawing of complete bipartite 
graphs in the plane such that every  edge crosses at most one edge.

 Key words:  planar graph, crossing number



[Full text:
 Preprint in Russian (.pdf.gz)


 
 







Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg