On the size of planarly connected crossing graphs

DOI10.7155/JGAA.00453zbMATH Open1377.05117arXiv1509.02475OpenAlexW2766243613MaRDI QIDQ4600734FDOQ4600734

Authors: Eyal Ackerman, Balázs Keszegh, Máté Vizer 

Publication date: 12 January 2018

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Abstract: We prove that if an $n$-vertex graph $G$ can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then $G$ has $O(n)$ edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal $1$-planar and fan-planar graphs.

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

Recommendations

• On the Size of Planarly Connected Crossing Graphs
• Quasi-planar graphs have a linear number of edges
• On the maximum number of edges in quasi-planar graphs
• Crossing numbers of beyond-planar graphs
• Graphs drawn with few crossings per edge

zbMATH Keywords

graph drawing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (13)

• The density of fan-planar graphs
• Crossing numbers of beyond-planar graphs
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Efficient generation of different topological representations of graphs beyond-planarity
• On the edge crossing properties of Euclidean minimum weight Laman graphs
• On RAC drawings of graphs with one bend per edge
• On the edge crossing properties of Euclidean minimum weight Laman graphs
• On the Size of Planarly Connected Crossing Graphs
• On RAC drawings of graphs with one bend per edge
• Quantitative restrictions on crossing patterns
• On the Crossing Number of Almost Planar Graphs
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Crossing Numbers of Beyond-Planar Graphs Revisited

This page was built for publication: On the size of planarly connected crossing graphs

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