An upper bound on the number of edges in an almost planar bipartite graph

DOI10.1007/S10958-014-1690-9zbMATH Open1298.05087arXiv1307.1013OpenAlexW3102811455MaRDI QIDQ744552FDOQ744552

Authors: D. Kharzeev 

Publication date: 25 September 2014

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Abstract: Let $G$ be a bipartite graph without loops and multiple edges on $vge4$ vertices, which can be drawn on the plane such that any edge intersects at most one other edge. We prove that such graph has at most $3v-8$ edges for even $ve6$ and at most $3v-9$ edges for odd $v$ and $v=6$. For all $vge4$ examples showing that these bounds are tight are constructed. In the end of paper we discuss a question about drawings of complete bipartite graphs on the plane such that any edge intersects at most one other edge. {sc Keywords:} topological graphs, planar graphs, bipartite graphs.

Full work available at URL: https://arxiv.org/abs/1307.1013

Recommendations

• On an extremal problem in the class of bipartite 1-planar graphs
• On the sizes of bipartite 1-planar graphs
• Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
• Quasi-planar graphs have a linear number of edges
• On the maximum number of edges in quasi-planar graphs

zbMATH Keywords

drawings of complete bipartite graphs on a plane

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Graphs drawn with few crossings per edge
• Quasi-planar graphs have a linear number of edges
• On the maximum number of edges in quasi-planar graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Geometric graphs with no self-intersecting path of length three
• Crossing Stars in Topological Graphs

Cited In (12)

• Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
• 1-Planar Graphs
• A note on the upper bounds on the size of bipartite and tripartite 1-embeddable graphs on surfaces
• Edge Partitions and Visibility Representations of 1-planar Graphs
• On the sizes of bipartite 1-planar graphs
• On plane bipartite graphs without fixed edges
• Title not available (Why is that?)
• On an extremal problem in the class of bipartite 1-planar graphs
• Equitable coloring in 1-planar graphs
• Large matchings in maximal 1-planar graphs
• An annotated bibliography on 1-planarity
• On the Size of Matchings in 1-Planar Graph with High Minimum Degree

This page was built for publication: An upper bound on the number of edges in an almost planar bipartite graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744552)