On the size of planarly connected crossing graphs

DOI10.7155/JGAA.00453MaRDI QIDQ4600734zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cited in

(13)

• Crossing Numbers of Beyond-Planar Graphs Revisited
• 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

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)