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

DOI10.1007/S10958-014-1690-9MaRDI QIDQ744552zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 25 September 2014

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

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

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)

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.

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

Cites work

• Crossing Stars in Topological Graphs
• Geometric graphs with no self-intersecting path of length three
• Graphs drawn with few crossings per edge
• 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
• Quasi-planar graphs have a linear number of edges

Cited in

(16)

• 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
• On the d-independence number in 1-planar graphs
• On an extremal problem in the class of bipartite 1-planar graphs
• An annotated bibliography on 1-planarity
• Equitable coloring in 1-planar graphs
• Large matchings in maximal 1-planar graphs
• On the Size of Matchings in 1-Planar Graph with High Minimum Degree
• On the independence number of 1-planar graphs
• On the edge density of bipartite 3-planar and bipartite gap-planar graphs
• Beyond-planarity: Turán-type results for non-planar bipartite graphs
• On the biplanar and k-planar crossing numbers

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)